spider graph 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 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 Maximum cut 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 binary tree ∩ partial grid

Unbounded on complete [by definition]
Unbounded on complete bipartite [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

branchwidth

Unbounded

[+]Details

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 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 Maximum cut 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 Superfactorial(Theta) Speed.
Unbounded From Superfactorial(Theta) Speed.
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 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 Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from booleanwidth
Unbounded from cliquewidth on the complement
Unbounded from rankwidth

Unbounded on bipartite permutation

Unbounded on chordal
Unbounded on co-comparability graphs of posets of interval dimension 2, height 2
Unbounded on permutation
Unbounded on permutation ∩ split
Unbounded on split
Unbounded on unit interval

cochromatic number

Unbounded

[+]Details

Unbounded from cochromatic number on the complement

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 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 Maximum cut 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 Superfactorial(Theta) Speed.
Unbounded From Superfactorial(Theta) Speed.
Unbounded from chromatic number
Unbounded from cochromatic number
Unbounded from maximum clique

Unbounded on complete bipartite [by definition]

diameter

Unbounded

[+]Details

Unbounded on SC 2-tree [trivial]
Unbounded on binary tree ∩ partial grid [trivial]
Unbounded on bipartite ∩ claw-free [by definition]
Unbounded on caterpillar [by definition]
Unbounded on linear forest [by definition]
Unbounded on unit interval [trivial]

distance to block

Unbounded

[+]Details

Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.

Unbounded on 2-tree
Unbounded on (3K1,P3)-free

Unbounded on bipartite ∩ claw-free [trivial]
Unbounded on complete bipartite [trivial]
Unbounded on complete split [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 Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut 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 Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to co-cluster on the complement
Unbounded from distance to cograph

Unbounded on complete bipartite [by definition]

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 from distance to cograph on the complement

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

Unbounded on 2K2-free ∩ bipartite
Unbounded on P4-reducible

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 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 Maximum cut 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

Unbounded on binary tree ∩ partial grid
Unbounded on caterpillar [trivial]

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 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 Maximum cut 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

Unbounded on 2-tree

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

Unbounded on complete bipartite [by definition]

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 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 Maximum cut 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]
Unbounded on hamiltonian ∩ interval [trivial]
Unbounded on hamiltonian ∩ split [trivial]
Unbounded on square of tree

maximum degree

Unbounded

[+]Details

Unbounded From Superfactorial(Theta) Speed.
Unbounded From Superfactorial(Theta) Speed.
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 (C4,P3,triangle)-free [by definition]
Unbounded on caterpillar [by definition]
Unbounded on complete [by definition]
Unbounded on complete bipartite [by definition]
Unbounded on disjoint union of stars [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 Hamiltonian cycle assuming Polynomial,NP-complete disjoint.
Unbounded from Hamiltonian path assuming Polynomial,NP-complete disjoint.
Unbounded from diameter
Unbounded from maximum induced matching
Unbounded from minimum dominating set

Unbounded on SC 2-tree [trivial]
Unbounded on SC 3-tree [trivial]
Unbounded on complete bipartite [by definition]
Unbounded on disjoint union of stars [by definition]
Unbounded on square of tree
Unbounded on unit Helly circle [trivial]

maximum induced matching

Unbounded

[+]Details

Unbounded from diameter

Unbounded on (P4,triangle)-free [by definition]
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 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 Maximum cut 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

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 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 Maximum cut 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

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 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 Maximum cut 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 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 Maximum cut assuming Linear,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 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 Maximum cut 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.