line graphs (original) (raw)

The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.

acyclic chromatic number

Unbounded

[+]Details

Unbounded from chromatic number
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique

bandwidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from carvingwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from cutwidth
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from maximum degree
Unbounded from pathwidth
Unbounded from rankwidth
Unbounded from treewidth

Unbounded on complete [by definition]

book thickness

Unbounded

[+]Details

Unbounded from acyclic chromatic number
Unbounded from chromatic number
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique

Unbounded on complete

booleanwidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from cliquewidth
Unbounded from rankwidth

branchwidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from rankwidth
Unbounded from treewidth

carvingwidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from maximum degree
Unbounded from rankwidth
Unbounded from treewidth

chromatic number

Unbounded

[+]Details

Unbounded from cochromatic number
Unbounded from maximum clique

cliquewidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Linear,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Linear,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Linear,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Linear,NP-complete disjoint.
Unbounded from booleanwidth
Unbounded from rankwidth

Unbounded on (C4,K4,claw,diamond)-free

Unbounded on Fn grid

cochromatic number

Unbounded

[+]Details

Unbounded on cluster

cutwidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from carvingwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from maximum degree
Unbounded from pathwidth
Unbounded from rankwidth
Unbounded from treewidth

degeneracy

Unbounded

[+]Details

Unbounded from chromatic number
Unbounded from cochromatic number
Unbounded from maximum clique

diameter

Unbounded

[+]Details

Unbounded on (C4,K4,claw,diamond)-free [trivial]
Unbounded on Fn grid [by definition]
Unbounded on bipartite ∩ claw-free [by definition]

distance to block

Unbounded

[+]Details

Unbounded on Fn grid [trivial]
Unbounded on bipartite ∩ claw-free [trivial]

distance to clique

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from cochromatic number
Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to cograph
Unbounded from maximum independent set
Unbounded from maximum induced matching
Unbounded from minimum clique cover
Unbounded from minimum dominating set

distance to cluster

Unbounded

[+]Details

Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to cograph

distance to co-cluster

Unbounded

[+]Details

Unbounded from diameter
Unbounded from distance to cluster on the complement
Unbounded from distance to cograph

distance to cograph

Unbounded

[+]Details

Unbounded from diameter

Unbounded on (2K2,C4,C5,claw,diamond)-free

distance to linear forest

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from distance to block
Unbounded from distance to outerplanar
Unbounded from maximum clique
Unbounded from pathwidth
Unbounded from rankwidth
Unbounded from treewidth

distance to outerplanar

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from rankwidth
Unbounded from treewidth

genus

Unbounded

[+]Details

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from chromatic number
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique

max-leaf number

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from bandwidth
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from carvingwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from cutwidth
Unbounded from degeneracy
Unbounded from distance to block
Unbounded from distance to linear forest
Unbounded from distance to outerplanar
Unbounded from maximum clique
Unbounded from maximum degree
Unbounded from pathwidth
Unbounded from rankwidth
Unbounded from treewidth

maximum clique

Unbounded

[+]Details

Unbounded on complete [by definition]

maximum degree

Unbounded

[+]Details

Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from chromatic number
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique

Unbounded on complete [by definition]

maximum independent set

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Linear,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from diameter
Unbounded from maximum induced matching
Unbounded from minimum dominating set

maximum induced matching

Unbounded

[+]Details

Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from diameter

Unbounded on cluster [trivial]
Unbounded on maximum degree 1 [trivial]

maximum matching

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to cograph
Unbounded from distance to linear forest
Unbounded from distance to outerplanar
Unbounded from maximum clique
Unbounded from maximum induced matching
Unbounded from pathwidth
Unbounded from rankwidth
Unbounded from tree depth
Unbounded from treewidth
Unbounded from vertex cover

minimum clique cover

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from cochromatic number
Unbounded from diameter
Unbounded from maximum independent set
Unbounded from maximum induced matching
Unbounded from minimum dominating set

minimum dominating set

Unbounded

[+]Details

Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from diameter

Unbounded on K2-free [by definition]

pathwidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from rankwidth
Unbounded from treewidth

rankwidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from booleanwidth
Unbounded from cliquewidth

tree depth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from diameter
Unbounded from maximum clique
Unbounded from pathwidth
Unbounded from rankwidth
Unbounded from treewidth

treewidth

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Linear,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Linear,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Linear,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from rankwidth

Unbounded on complete [by definition]

vertex cover

Unbounded

[+]Details

Unbounded from 3-Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Clique cover assuming Polynomial,NP-complete disjoint.
Unbounded from Colourability assuming Polynomial,NP-complete disjoint.
Unbounded from Domination assuming Polynomial,NP-complete disjoint.
Unbounded from Feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Graph isomorphism assuming Polynomial,GI-complete disjoint.
Unbounded from Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted feedback vertex set assuming Polynomial,NP-complete disjoint.
Unbounded from Weighted independent dominating set assuming Polynomial,NP-complete disjoint.
Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from booleanwidth
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from cliquewidth
Unbounded from cochromatic number
Unbounded from degeneracy
Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to cograph
Unbounded from distance to linear forest
Unbounded from distance to outerplanar
Unbounded from maximum clique
Unbounded from maximum induced matching
Unbounded from maximum matching
Unbounded from pathwidth
Unbounded from rankwidth
Unbounded from tree depth
Unbounded from treewidth

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.

3-Colourability

NP-complete

[+]Details

NP-complete on (K4,claw,diamond)-free
NP-complete
NP-complete on linear domino ∩ maximum degree 4

Clique

Polynomial

[+]Details

Polynomial from Independent set on the complement
Polynomial from Weighted clique

Clique cover

NP-complete

[+]Details

NP-complete on line graphs of triangle-free graphs

Colourability

NP-complete

[+]Details

NP-complete from 3-Colourability

NP-complete on (K4,claw,diamond)-free

Domination

NP-complete

[+]Details

NP-complete

Feedback vertex set

NP-complete

[+]Details

NP-complete on line graphs of planar cubic bipartite graphs

Graph isomorphism

GI-complete

[+]Details

GI-complete on (C4,claw,diamond)-free
GI-complete
GI-complete on line graphs of bipartite graphs

Hamiltonian cycle

NP-complete

[+]Details

NP-complete
NP-complete on line graphs of bipartite graphs

Hamiltonian path

NP-complete

[+]Details

NP-complete
NP-complete on line graphs of bipartite graphs

Independent dominating set

NP-complete

[+]Details

NP-complete

On domination perfect graphs, the Domination and Independent dominating set problems are equivalent.

Independent set

Polynomial

[+]Details

Polynomial from Weighted independent set

Polynomial on (E,P)-free

Polynomial on EPT
Polynomial on (P,T2)-free
Polynomial on (P,star1,2,5)-free
Polynomial on claw-free

Maximum cut

Polynomial

[+]Details

Polynomial

Monopolarity

Linear

[+]Details

Linear
Polynomial [$O(V^4)$] on (5-pan,T2,X172)-free
Polynomial [$O(V^3)$] on claw-free

Polarity

Linear

[+]Details

Linear

Recognition

Linear

[+]Details

Linear
Polynomial on (K5 - e,W5,A,C4 ∪ 2K1,P2 ∪ P3,R,claw,co-twin-C5,co-twin-house)-free