Graphclass: (X₄₂,T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,net)-free

Complement classes

(S₃,T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,X₄₂)-free

Forbidden subgraphs

X₄₂X_{42} T₂\co{T_2} X₂₀₅\co{X_{205}} X₂₀₆\co{X_{206}} X₂₀₇\co{X_{207}} X₂₀₈ (figure shows X₂₀₈) \co{X_{208}} netnet

Inclusions

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.

Map

Inclusion map for (X_{42},\co{T_2},\co{X_{205}},\co{X_{206}},\co{X_{207}},\co{X_{208}},net)--free

Minimal superclasses

net-free [from the set of forbidden subgraphs] (known proper)

Maximal subclasses

(2K₃ + e,3K₁,C₅,T₂,X₁₈,X₉₄,co-domino)-free [from the set of forbidden subgraphs] (known proper)
(2K₃,2K₃ + e,3K₁,A,H,T₂,X₁₈,X₄₅,co-domino)-free [from the set of forbidden subgraphs] (known proper)
(3K₁,C₅,K₃ ∪ K₄,BW₃,K_3,4-e,T₂,X₁₈,X₉₂,X₉₃)-free [from the set of forbidden subgraphs] (known proper)
(3K₁,E)-free [from the set of forbidden subgraphs] (known proper)
(3K₂,A,C₄ ∪ 2K₁,E,P₂ ∪ P₃,R,K₅ - e,co-claw,net,odd anti-hole,twin-house)-free [from the set of forbidden subgraphs] (known proper)
(3K₂,C₅,P₂ ∪ P₄,XZ₁₁,XZ₁₂,XZ₁₃,XZ₁₄,XZ₆,XZ₇,XZ₈,XZ₉,XZ₁₁,XZ₁₂,XZ₁₃,XZ₁₄,XZ₆,XZ₇,XZ₈,XZ₉,net)-free [from the set of forbidden subgraphs] (known proper)
(A,E,S₃,X₁,domino,hole,house,net,rising sun)-free [from the set of forbidden subgraphs] (known proper)
(C₅,P₅,P,co-fork,co-gem,fork)-free [from the set of forbidden subgraphs] (known proper)
(C₆,K₂ ∪ K₃,X₁₀₃,X₃₇,X₈₈,X₉₀,C_n+4 ∪ K₁,T₂,net ∪ K₁,co-diamond,co-domino,co-eiffeltower,co-twin-C₅)-free [from the set of forbidden subgraphs] (known proper)
(C₆,K₂ ∪ K₃,X₃₇,X₉₀,C_n+4 ∪ K₁,T₂,W_n+4,X₃₁,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-domino,co-twin-C₅)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4 ∪ K₁,K_2,3,T₂,W_n+4,X₃₁,XF₂ⁿ⁺¹,XF₃ⁿ,C₆,X₃₇,X₉₀,domino,twin-C₅)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4 ∪ K₁,S₃ ∪ K₁,X₄₂,T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,odd-cycle ∪ K₁,even anti-hole,net)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4,S₃,net)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4,T₂,net)-free [from the set of forbidden subgraphs] (known proper)
(K₂ ∪ K₃,X₉₀,C_n+4 ∪ K₁,T₂,co-domino,co-paw,co-twin-C₅)-free [from the set of forbidden subgraphs] (known proper)
(P,co-fork,co-gem)-free [from the set of forbidden subgraphs] (known proper)
P₄-extendible (possibly equal)
P₄-indifference (known proper)
(P₅,S₃,A,E,X₁,anti-hole,co-domino,co-rising sun,net)-free [from the set of forbidden subgraphs] (known proper)
(S₃,co-claw,net)-free [from the set of forbidden subgraphs] (known proper)
(S₃,net)-free ∩ chordal (known proper)
(X₄₂,T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,net)-free ∩ normal circular arc ∩ quasi-line (known proper)
(XC₁,XC₂,XC₃,XC₄,XC₅,XC₆,XC₇,XC₈)-free [from the set of forbidden subgraphs] (known proper)
(XC₇,XC₁,XC₂,XC₃,XC₄,XC₅,XC₆,XC₈)-free [from the set of forbidden subgraphs] (known proper)
(A,T₂,odd anti-cycle)-free [from the set of forbidden subgraphs] (known proper)
(W₄,co-claw,co-gem)-free [from the set of forbidden subgraphs] (known proper)
τ_k-perfect for all k >= 2 (known proper)
(bull,co-fork)-free [from the set of forbidden subgraphs] (known proper)
(bull,fork,gem)-free [from the set of forbidden subgraphs] (known proper)
(bull,house)-free [from the set of forbidden subgraphs] (known proper)
chordal ∩ diametral path (known proper)
(co-gem,gem)-free [from the set of forbidden subgraphs] (known proper)
(co-gem,house)-free [from the set of forbidden subgraphs] (known proper)
co-interval ∪ interval (possibly equal)
comparability ∩ distance-hereditary (known proper)
concave-round (known proper)
(domino,gem,hole,house,net)-free [from the set of forbidden subgraphs] (known proper)
normal Helly circular arc (known proper)
strict 2-threshold (known proper)

Speed

[?]

The speed of a class $X$ is the function $n \mapsto |X_n|,ドル where $X_n$ is the set of $n$-vertex labeled graphs in $X$.

Depending on the rate of growths of the speed of the class, ISGCI distinguishes the following values of the parameter:
Constant
Polynomial
Exponential
Factorial
Superfactorial (2ドル^{o(n^2)}$ )
Superfactorial (2ドル^{\Theta(n^2)}$ )

superfactorial (2ドル^{\Theta(n^2)}$)

at least factorial on P₄-free

[1791]

V.V. Lozin, C. Mayhill, V. Zamaraev
Locally bounded coverings and factorial properties of graphs
European J. Combin. 33 No.4 534-543 (2012)

at least superfactorial (2ドル^{\Theta(n^2)}$) on bipartite

[1788]

V.E. Alekseev
Range of values of entropy of hereditary classes of graphs
Diskretn. Math. 4:2 148-157 (1995)

[1789]

B. Bollobas, A. Thomason
Projections of bodies and hereditary properties of hypergraphs
Bull. London Math. Soc. 27(5) 417-424 (1995)

Parameters

acyclic chromatic number

[?]

The acyclic chromatic number of a graph $G$ is the smallest size of a vertex partition $\{V_1,\dots,V_l\}$ such that each $V_i$ is an independent set and for all $i,j$ that graph $G[V_i\cup V_j]$ does not contain a cycle.

Unbounded

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

Unbounded on C₄-free ∩ C₆-free ∩ bipartite

[1760]

(no preview available)

bandwidth

[?]

The bandwidth of a graph $G$ is the shortest maximum "length" of an edge over all one dimensional layouts of $G$. Formally, bandwidth is defined as $\min_{i \colon V \rightarrow \mathbb{N}\;}\{\max_{\{u,v\}\in E\;} \{|i(u)-i(v)|\}\mid i\text{ is injective}\}$.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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 binary tree ∩ partial grid

[1757]

(no preview available)

Unbounded on complete [by definition]
Unbounded on complete bipartite [by definition]
Unbounded on grid graph ∩ maximum degree 3

[1757]

(no preview available)

book thickness

[?]

A book embedding of a graph $G$ is an embedding of $G$ on a collection of half-planes (called pages) having the same line (called spine) as their boundary, such that the vertices all lie on the spine and there are no crossing edges. The book thickness of a graph $G$ is the smallest number of pages over all book embeddings of $G$.

Unbounded

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

Unbounded on complete

[1778]

F. Bernhart, P.C. Kainen
The book thickness of a graph
J. of Combin. Th. (B) 27 320-331 (1979)

booleanwidth

[?]

Consider the following decomposition of a graph $G$ which is defined as a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. The function $\text{cut-bool} \colon 2^{V(G)} \rightarrow R$ is defined as $\text{cut-bool}(A)$ := $\log_2|\{S \subseteq V(G) \backslash A \mid \exists X \subseteq A \colon S = (V(G) \backslash A) \cap \bigcup_{x \in X} N(x)\}|$. Every edge $e$ in $T$ partitions the vertices $V(G)$ into $\{A_e,\overline{A_e}\}$ according to the leaves of the two connected components of $T - e$. The booleanwidth of the above decomposition $(T,L)$ is $\max_{e \in E(T)\;} \{ \text{cut-bool}(A_e)\}$. The booleanwidth of a graph $G$ is the minimum booleanwidth of a decomposition of $G$ as above.

Unbounded

branchwidth

[?]

A branch decomposition of a graph $G$ is a pair $(T,\chi),ドル where $T$ is a binary tree and $\chi$ is a bijection, mapping leaves of $T$ to edges of $G$. Any edge $\{u, v\}$ of the tree divides the tree into two components and divides the set of edges of $G$ into two parts $X, E \backslash X,ドル consisting of edges mapped to the leaves of each component. The width of the edge $\{u,v\}$ is the number of vertices of $G$ that is incident both with an edge in $X$ and with an edge in $E \backslash X$. The width of the decomposition $(T,\chi)$ is the maximum width of its edges. The branchwidth of the graph $G$ is the minimum width over all branch-decompositions of $G$.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

Consider a decomposition $(T,\chi)$ of a graph $G$ where $T$ is a binary tree with $|V(G)|$ leaves and $\chi$ is a bijection mapping the leaves of $T$ to the vertices of $G$. Every edge $e \in E(T)$ of the tree $T$ partitions the vertices of the graph $G$ into two parts $V_e$ and $V \backslash V_e$ according to the leaves of the two connected components in $T - e$. The width of an edge $e$ of the tree is the number of edges of a graph $G$ that have exactly one endpoint in $V_e$ and another endpoint in $V \backslash V_e$. The width of the decomposition $(T,\chi)$ is the largest width over all edges of the tree $T$. The carvingwidth of a graph is the minimum width over all decompositions as above.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

The chromatic number of a graph is the minimum number of colours needed to label all its vertices in such a way that no two vertices with the same color are adjacent.

Unbounded

Unbounded from cochromatic number
Unbounded from maximum clique

Unbounded on girth>=9

[1734]

P. Erdos
Graph theory and probability
Canadian J. of Math. 11 34-38 (1959)

Unbounded on triangle-free

[1734]

P. Erdos
Graph theory and probability
Canadian J. of Math. 11 34-38 (1959)

cliquewidth

[?]

The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

creation of a vertex with label $i,ドル
disjoint union,
renaming labels $i$ to label $j,ドル and
connecting all vertices with label $i$ to all vertices with label $j$.

Unbounded

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 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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent set assuming Linear,NP-complete disjoint.
Unbounded from booleanwidth
Unbounded from cliquewidth on the complement
Unbounded from rankwidth

Unbounded on C₄-free ∩ C₆-free ∩ bipartite

[1183]

R. Boliac, V.V. Lozin
On the clique-width of graphs in hereditary classes.
Rutcor Research Report RRR 14-2002

Unbounded on (C₅,P₅,P,co-fork,co-gem,fork)-free

[1185]

A. Brandstaedt, F.F. Dragan, H.-O. Le, R. Mosca
New graph classes of bounded clique-width
WG 2002, Lecture Notes in Computer Science 2573, 57-67 (2002)

Unbounded on H_n,q grid

[1176]

J.A. Makowsky, U. Rotics
On the clique-width of graphs with few $P_4$'s.
International Journal of Foundations of Computer Science 10 (1999) 329-348

Unbounded on bipartite permutation

[1182]

A. Brandstaedt, V.V. Lozin
On the linear structure and clique-width of bipartite permutation graphs.
Accepted for Ars Combinatorica

Unbounded on co-interval
Unbounded on grid

[1177]

Golumbic, Martin Charles; Rotics, Udi
On the clique-width of perfect graph classes (extended abstract) .
Graph theoretic concepts in computer science. 25th international workshop, WG '99 Ascona, Switzerland, June 17-19, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1665, 135-147 (1999)

Unbounded on permutation ∩ split

[1796]

N. Korpelainen, V.V. Lozin, C. Mayhill
Split permutation graphs
Graphs and Combinatorics 30 633-646 (2014)

Unbounded on unit interval

[1177]

cochromatic number

[?]

The cochromatic number of a graph $G$ is the minimum number of colours needed to label all its vertices in such a way that that every set of vertices with the same colour is either independent in G, or independent in $\overline{G}$.

Unbounded

Unbounded from cochromatic number on the complement

Unbounded on cluster

[1866]

(no preview available)

Unbounded on girth>=9

[1866]

(no preview available)

cutwidth

[?]

The cutwidth of a graph $G$ is the smallest integer $k$ such that the vertices of $G$ can be arranged in a linear layout $v_1, \ldots, v_n$ in such a way that for every $i = 1, \ldots,n - 1,ドル there are at most $k$ edges with one endpoint in $\{v_1, \ldots, v_i\}$ and the other in $\{v_{i+1}, \ldots, v_n\}$.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

Let $G$ be a graph and consider the following algorithm:

Find a vertex $v$ with smallest degree.
Delete vertex $v$ and its incident edges.
Repeat as long as the graph is not empty.

The degeneracy of a graph $G$ is the maximum degree of a vertex when it is deleted in the above algorithm.

Unbounded

Unbounded From Superfactorial(Theta) Speed.
Unbounded From Superfactorial(Theta) Speed.
Unbounded from chromatic number
Unbounded from cochromatic number
Unbounded from maximum clique

Unbounded on C₄-free ∩ C₆-free ∩ bipartite
Unbounded on complete bipartite [by definition]
Unbounded on hypercube [by definition]

diameter

[?]

The diameter of a graph $G$ is the length of the longest shortest path between any two vertices in $G$.

Unbounded

Unbounded on 2-subdivision ∩ planar [by definition]
Unbounded on H_n,q grid [by definition]
Unbounded on binary tree ∩ partial grid [trivial]
Unbounded on bipartite ∩ claw-free [by definition]
Unbounded on caterpillar [by definition]
Unbounded on grid graph ∩ maximum degree 3 [trivial]
Unbounded on unit interval [trivial]

distance to block

[?]

The distance to block of a graph $G$ is the size of a smallest vertex subset whose deletion makes $G$ a block graph.

Unbounded

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

Unbounded on 2-subdivision ∩ planar [trivial]
Unbounded on (3K₁,P₃)-free

[1827]

(no preview available)

Unbounded on H_n,q grid [trivial]
Unbounded on bipartite ∩ claw-free [trivial]
Unbounded on bipartite ∩ girth>=9 ∩ maximum degree 3 ∩ planar
Unbounded on complete bipartite [trivial]
Unbounded on complete split [trivial]

distance to clique

[?]

Let $G$ be a graph. Its distance to clique is the minimum number of vertices that have to be deleted from $G$ in order to obtain a clique.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Monopolarity 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 Weighted independent 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

[?]

A cluster is a disjoint union of cliques. The distance to cluster of a graph $G$ is the size of a smallest vertex subset whose deletion makes $G$ a cluster graph.

Unbounded

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

[?]

The distance to co-cluster of a graph is the minimum number of vertices that have to be deleted to obtain a co-cluster graph.

Unbounded

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

distance to cograph

[?]

The distance to cograph of a graph $G$ is the minimum number of vertices that have to be deleted from $G$ in order to obtain a cograph .

Unbounded

Unbounded from diameter
Unbounded from distance to cograph on the complement

Unbounded on 2K₂-free ∩ bipartite
Unbounded on P₄-reducible
Unbounded on (P₅,triangle)-free

distance to linear forest

[?]

The distance to linear forest of a graph $G = (V, E)$ is the size of a smallest subset $S$ of vertices, such that $G[V \backslash S]$ is a disjoint union of paths and singleton vertices.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

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

distance to outerplanar

[?]

The distance to outerplanar of a graph $G = (V,E)$ is the minumum size of a vertex subset $X \subseteq V,ドル such that $G[V \backslash X]$ is a outerplanar graph.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

The genus $g$ of a graph $G$ is the minimum number of handles over all surfaces on which $G$ can be embedded without edge crossings.

Unbounded

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 2-subdivision [trivial]
Unbounded on bipartite ∩ maximum degree 3
Unbounded on complete bipartite [by definition]

max-leaf number

[?]

The max-leaf number of a graph $G$ is the maximum number of leaves in a spanning tree of $G$.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

The parameter maximum clique of a graph $G$ is the largest number of vertices in a complete subgraph of $G$.

Unbounded

Unbounded on complete [by definition]
Unbounded on hamiltonian ∩ interval [trivial]

maximum degree

[?]

The maximum degree of a graph $G$ is the largest number of neighbors of a vertex in $G$.

Unbounded

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 2-subdivision ∩ planar [by definition]
Unbounded on (C₄,P₃,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

[?]

An independent set of a graph $G$ is a subset of pairwise non-adjacent vertices. The parameter maximum independent set of graph $G$ is the size of a largest independent set in $G$.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Monopolarity 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 Weighted independent set assuming Polynomial,NP-complete disjoint.
Unbounded from diameter
Unbounded from maximum induced matching
Unbounded from minimum dominating set

Unbounded on 2-subdivision [by definition]
Unbounded on complete bipartite [by definition]
Unbounded on disjoint union of stars [by definition]

maximum induced matching

[?]

For a graph $G = (V,E)$ an induced matching is an edge subset $M \subseteq E$ that satisfies the following two conditions: $M$ is a matching of the graph $G$ and there is no edge in $E \backslash M$ connecting any two vertices belonging to edges of the matching $M$. The parameter maximum induced matching of a graph $G$ is the largest size of an induced matching in $G$.

Unbounded

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

Unbounded on (P₄,triangle)-free [by definition]
Unbounded on cluster [trivial]
Unbounded on maximum degree 1 [trivial]

maximum matching

[?]

A matching in a graph is a subset of pairwise disjoint edges (any two edges that do not share an endpoint). The parameter maximum matching of a graph $G$ is the largest size of a matching in $G$.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

A clique cover of a graph $G = (V, E)$ is a partition $P$ of $V$ such that each part in $P$ induces a clique in $G$. The minimum clique cover of $G$ is the minimum number of parts in a clique cover of $G$. Note that the clique cover number of a graph is exactly the chromatic number of its complement.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Monopolarity 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 Weighted independent 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

[?]

A dominating set of a graph $G$ is a subset $D$ of its vertices, such that every vertex not in $D$ is adjacent to at least one member of $D$. The parameter minimum dominating set for graph $G$ is the minimum number of vertices in a dominating set for $G$.

Unbounded

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

Unbounded on K₂-free [by definition]

pathwidth

[?]

A path decomposition of a graph $G$ is a pair $(P,X)$ where $P$ is a path with vertex set $\{1, \ldots, q\},ドル and $X = \{X_1,X_2, \ldots ,X_q\}$ is a family of vertex subsets of $V(G)$ such that:

$\bigcup_{p \in \{1,\ldots ,q\}} X_p = V(G)$
$\forall\{u,v\} \in E(G) \exists p \colon u, v \in X_p$
$\forall v \in V(G)$ the set of vertices $\{p \mid v \in X_p\}$ is a connected subpath of $P$.

The width of a path decomposition $(P,X)$ is max$\{|X_p| - 1 \mid p \in \{1,\ldots ,q\}\}$. The pathwidth of a graph $G$ is the minimum width among all possible path decompositions of $G$.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

Let $M$ be the $|V| \times |V|$ adjacency matrix of a graph $G$. The cut rank of a set $A \subseteq V(G)$ is the rank of the submatrix of $M$ induced by the rows of $A$ and the columns of $V(G) \backslash A$. A rank decomposition of a graph $G$ is a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. Any edge $e$ in the tree $T$ splits $V(G)$ into two parts $A_e, B_e$ corresponding to the leaves of the two connected components of $T - e$. The width of an edge $e \in E(T)$ is the cutrank of $A_e$. The width of the rank-decomposition $(T,L)$ is the maximum width of an edge in $T$. The rankwidth of the graph $G$ is the minimum width of a rank-decomposition of $G$.

Unbounded

tree depth

[?]

A tree depth decomposition of a graph $G = (V,E)$ is a rooted tree $T$ with the same vertices $V,ドル such that, for every edge $\{u,v\} \in E,ドル either $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$ in the tree $T$. The depth of $T$ is the maximum number of vertices on a path from the root to any leaf. The tree depth of a graph $G$ is the minimum depth among all tree depth decompositions.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

[?]

A tree decomposition of a graph $G$ is a pair $(T, X),ドル where $T = (I, F)$ is a tree, and $X = \{X_i \mid i \in I\}$ is a family of subsets of $V(G)$ such that

the union of all $X_i,ドル $i \in I$ equals $V,ドル
for all edges $\{v,w\} \in E,ドル there exists $i \in I,ドル such that $v, w \in X_i,ドル and
for all $v \in V$ the set of nodes $\{i \in I \mid v \in X_i\}$ forms a subtree of $T$.

The width of the tree decomposition is $\max |X_i| - 1$.
The treewidth of a graph is the minimum width over all possible tree decompositions of the graph.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Linear,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent set 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

[?]

Let $G$ be a graph. Its vertex cover number is the minimum number of vertices that have to be deleted in order to obtain an independent set.

Unbounded

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 Independent set assuming Polynomial,NP-complete disjoint.
Unbounded from Maximum cut assuming Polynomial,NP-complete disjoint.
Unbounded from Polarity 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 Weighted independent 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

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

Parameter decomposition

book thickness decomposition

[?]

Input: A graph G in this class and an integer k.

Output: True iff the book thickness of G is at most k.

Unknown to ISGCI

booleanwidth decomposition

[?]

Input: A graph G in this class.

Output: An expression that constructs G according to the rules for booleanwidth, using only a constant number of labels.
Undefined if this class has unbounded booleanwidth.

Unknown to ISGCI

cliquewidth decomposition

[?]

Input: A graph G in this class.

Output: An expression that constructs G according to the rules for cliquewidth, using only a constant number of labels.
Undefined if this class has unbounded cliquewidth.

Unknown to ISGCI

cutwidth decomposition

[?]

Input: A graph G in this class and an integer k.

Output: True iff the cutwidth of G is at most k.

NP-complete

Unbounded/NP-complete on 2-subdivision ∩ planar
Unbounded/NP-complete on grid graph

[1511]

J. Diaz, M. Penrose, J. Petit, M. Serna
Approximating layout problems on random geometric graphs
Journal of Algorithms 39 78-117 (2001)

treewidth decomposition

[?]

Input: A graph G in this class and an integer k.

Output: True iff the treewidth of G is at most k.

NP-complete

Unbounded/NP-complete on bipartite

[119]

H.L. Bodlaender
A tourist guide through treewidth
Acta Cybernetica 11 1993 1--23

Unbounded/NP-complete on perfect elimination bipartite

[1729]

T. Liu
Restricted Bipartite Graphs: Comparison and Hardness Results
Algorithmic Aspects in Information and Management (AAIM 2014) LNCS 8546, 241-252 (2014)

Unweighted problems

3-Colourability

[?]

Input: A graph G in this class.

Output: True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.

NP-complete

NP-complete on (K_1,5,triangle)-free

[1426]

F. Maffray, M. Preissmann
On the NP-completeness of the k-colorability problem for triangle-free graphs
Discrete Math. 162 No.1-3 313-317 (1996)

NP-complete on girth>=9

[1747]

(no preview available)

Clique

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.

Unknown to ISGCI

Clique cover

[?]

Input: A graph G in this class and an integer k.

Output: True iff the vertices of G can be partitioned into k sets S_i, such that whenever two vertices are in the same set S_i, they are adjacent.

NP-complete

NP-complete from Colourability on the complement

Colourability

[?]

Input: A graph G in this class and an integer k.

Output: True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.

NP-complete

NP-complete from 3-Colourability
NP-complete from Clique cover on the complement

NP-complete on (C₄,triangle)-free

[1433]

D. Kral, J. Kratochvil, Z. Tuza, G.J. Woeginger
Complexity of coloring graphs without forbidden induced subgraphs
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 254-262 (2001)

NP-complete on (K_1,5,triangle)-free

[1426]

F. Maffray, M. Preissmann
On the NP-completeness of the k-colorability problem for triangle-free graphs
Discrete Math. 162 No.1-3 313-317 (1996)

[1433]

NP-complete on triangle-free

[1426]

F. Maffray, M. Preissmann
On the NP-completeness of the k-colorability problem for triangle-free graphs
Discrete Math. 162 No.1-3 313-317 (1996)

[1433]

[420]

M.R. Garey, D.S. Johnson
Computers and Intractability -- A Guide to the Theory of \NP--completeness
Freeman and Company, San Francisco 1979

Domination

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

NP-complete

NP-complete on (C₄,C₅,C₆,C₇,C₈,H,X₈₅,triangle)-free ∩ K_1,4-free

[1666]

I.E. Zverovich, O.I. Zverovich
Independent Domination in hereditary classes
Theoretical Comp. Sci. 352 215-225 (2006)

NP-complete on bipartite

[1142]

A.K. Dewdney
Fast turing reductions between problems in NP; chapter 4; reductions between NP-complete problems.
Technical Report 71, Dept. Computer Science, University of Western Ontario 1981

NP-complete on bipartite ∩ girth>=9 ∩ maximum degree 3 ∩ planar

[1096]

I.E. Zverovich, V.E. Zverovich
An induced subgraph characterization of domination perfect graphs
J. Graph Theory 20 1995 375--395

NP-complete on bipartite ∩ maximum degree 3

[1446]

(no preview available)

NP-complete on chordal bipartite

[1156]

Mueller, Haiko; Brandstaedt, Andreas
The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs.
Theor. Comput. Sci. 53, 257-265 (1987)

NP-complete on domination perfect ∩ triangle-free

[1096]

I.E. Zverovich, V.E. Zverovich
An induced subgraph characterization of domination perfect graphs
J. Graph Theory 20 1995 375--395

NP-complete on grid graph

[229]

B.N. Clark, C.J. Colbourn, D.S. Johnson
Unit disk graphs
Discrete Math. 86 1990 165--177

NP-complete on partial grid

[1162]

Berman, Fran; Johnson, David; Leighton, Tom; Shor, Peter W.; Snyder, Larry
Generalized planar matching.
J. Algorithms 11, No.2, 153-184 (1990)

[630]

D.S. Johnson
The \NP--completeness column: an ongoing guide
J. Algorithms 6 145--159, 291--305, 434--451 1985

Feedback vertex set

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.

NP-complete

NP-complete on 2-subdivision

[1648]

(no preview available)

NP-complete on 2-subdivision ∩ planar

[1648]

(no preview available)

NP-complete on bipartite ∩ maximum degree 4 ∩ planar

[1593]

(no preview available)

NP-complete on bipartite ∩ planar

[1584]

A. Takaoka, S. Tayu, S. Ueno
On minimum feedback vertex set in graphs
Third Internation Conference on Networking and Computing 429-434 (2012)

NP-complete on perfect elimination bipartite

[1729]

T. Liu
Restricted Bipartite Graphs: Comparison and Hardness Results
Algorithmic Aspects in Information and Management (AAIM 2014) LNCS 8546, 241-252 (2014)

NP-complete on star convex

[1590]

W. Jiang, T. Liu, T. Ren, K. Xu
Two hardness results on feedback vertex sets
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management; Lecture Notes in Computer Science 6681 233-243 (2011)

NP-complete on tree convex

[1580]

C. Wang, T. Liu, W. Jian, K. Xu
Feedback vertex set on tree convex bipartite graphs
Proceedings of COCOA 2012 LNCS 7402 95-102 (2012)

Graph isomorphism

[?]

Input: Graphs G and H in this class

Output: True iff G and H are isomorphic.

GI-complete

GI-complete from Graph isomorphism on the complement

GI-complete on 2-subdivision

[1675]

(no preview available)

GI-complete on chordal bipartite

[1689]

R. Uehara, S. Toda, T. Nagoya
Graph isomorphism completenes for chordal bipartite graphs and strongly chordal graphs
Discrete Appl. Math. 145 No.3 479-482

Hamiltonian cycle

[?]

Input: A graph G in this class.

Output: True iff G has a simple cycle that goes through every vertex of the graph.

NP-complete

NP-complete on bipartite

[1533]

M.S. Krisnamoorthy
An NP-hard problem in bipartite graphs
SIGACT News 7 26-26 (1976)

NP-complete on bipartite ∩ cubic ∩ planar

[1810]

A. Munaro
On line graphs of subcubic triangle-free graphs
Discrete Math. 340 No.6 1210-1226 (2017)

NP-complete on bipartite ∩ girth>=9 ∩ maximum degree 3 ∩ planar

[1675]

(no preview available)

NP-complete on bipartite ∩ maximum degree 3 ∩ planar

[1523]

T. Akiyama, T. Nishizeki, N. Saito
NP-completeness of the Hamiltonian cycle problem for bipartite graphs
J. Inf. Process. V.3 73-76 (1980)

[1537]

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

NP-complete on chordal bipartite

[1517]

H. Mueller
Hamiltonian circuits in chordal bipartite graphs
Discrete Math. 156 291-298 (1996)

NP-complete on girth>=9

[1675]

(no preview available)

NP-complete on grid graph

[1537]

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

[229]

B.N. Clark, C.J. Colbourn, D.S. Johnson
Unit disk graphs
Discrete Math. 86 1990 165--177

NP-complete on grid graph ∩ maximum degree 3

[1537]

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

[1565]

E.M. Arkin, S.P. Fekete, K. Islam, H. Meijer, J.S.B. Mitchell, Y. Nunez-Rodriguez, V. Polishchuk, D. Rappaport, H. Xiao
A study of grid hamiltonicity: Not being (super)thin or solid is hard
Computational Geometry: Theory and Applications 42 No.6-7 582-605 (2009)

NP-complete on star convex

[1655]

(no preview available)

Hamiltonian path

[?]

Input: A graph G in this class.

Output: True iff G has a simple path that goes through every vertex of the graph.

NP-complete

NP-complete on bipartite ∩ cubic ∩ planar

[1810]

A. Munaro
On line graphs of subcubic triangle-free graphs
Discrete Math. 340 No.6 1210-1226 (2017)

NP-complete on bipartite ∩ girth>=9 ∩ maximum degree 3 ∩ planar

[1675]

(no preview available)

NP-complete on chordal bipartite

[1517]

H. Mueller
Hamiltonian circuits in chordal bipartite graphs
Discrete Math. 156 291-298 (1996)

NP-complete on girth>=9

[1675]

(no preview available)

NP-complete on grid graph

[1537]

A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter
Hamiltonian paths in grid graphs
SIAM J. Comput. Vol.11 No.4 676-686 (1982)

NP-complete on grid graph ∩ maximum degree 3

[1653]

C.H. Papadimitriou, U.V. Vazirani
On two geometric problems related to the travelling salesman problem
J. of Algorithms 5 No.2 231-246 (1984)

NP-complete on star convex

[1655]

(no preview available)

Independent dominating set

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of pairwise non-adjacent vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

NP-complete

NP-complete on (C₄,C₅,C₆,C₇,C₈,H,X₈₅,triangle)-free ∩ K_1,4-free

[1666]

I.E. Zverovich, O.I. Zverovich
Independent Domination in hereditary classes
Theoretical Comp. Sci. 352 215-225 (2006)

NP-complete on bipartite ∩ girth>=9 ∩ maximum degree 3 ∩ planar

[1096]

I.E. Zverovich, V.E. Zverovich
An induced subgraph characterization of domination perfect graphs
J. Graph Theory 20 1995 375--395

Independent set

[?]

Input: A graph G in this class and an integer k.

Output: True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.

NP-complete

NP-complete on 2-subdivision
NP-complete on 2-subdivision ∩ planar
NP-complete on (C₄,C₅,C₆,C₇,C₈,H,X₈₅,triangle)-free ∩ K_1,4-free

Maximum cut

[?]

(decision variant)

Input: A graph G in this class and an integer k.

Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.

NP-complete

NP-complete on 2-subdivision

[1648]

(no preview available)

NP-complete on interval

[1815]

R. Adhikary, K. Bose, S. Mukherjee, B. Roy
Complexity of maximum cut on interval graphs
Proc. of 37th International Symposium on Computation Geometry 7:1-7:11 (2021)

Monopolarity

[?]

Input: A graph G in this class.

Output: True iff G is monopolar.

NP-complete

NP-complete on maximum degree 3 ∩ planar ∩ triangle-free

[1764]

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

NP-complete on triangle-free

[1768]

R. Churchley, J. Huang
On the polarity and monopolarity of graphs
J. Graph Theory 76 No. 2 1138-148 (2014)

Polarity

[?]

Input: A graph G in this class.

Output: True iff G is polar.

NP-complete

NP-complete on maximum degree 3 ∩ planar ∩ triangle-free

[1764]

V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

NP-complete on triangle-free

[1768]

R. Churchley, J. Huang
On the polarity and monopolarity of graphs
J. Graph Theory 76 No. 2 1138-148 (2014)

Recognition

[?]

Input: A graph G.

Output: True iff G is in this graph class.

Polynomial

Finite forbidden subgraph characterization

Weighted problems

Weighted clique

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

Unknown to ISGCI

Weighted feedback vertex set

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.

NP-complete

NP-complete from Feedback vertex set

Weighted independent dominating set

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.

NP-complete

NP-complete from Independent dominating set

Weighted independent set

[?]

Input: A graph G in this class with weight function on the vertices and a real k.

Output: True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.

NP-complete

NP-complete from Independent set

Weighted maximum cut

[?]

(decision variant)

Input: A graph G in this class with weight function on the edges and a real k.

Output: True iff the vertices of G can be partitioned into two sets A,B such that the sum of weights of the edges in G with one endpoint in A and the other endpoint in B is at least k.

NP-complete

NP-complete from Maximum cut

NP-complete on 2K₁-free

[1676]

M. Kaminski
Max-cut and containment relations in graphs
Proceedings of WG 2010, Lecture Notes in Computer Science 6410, 15-26 (2010)

NP-complete on P₃-free

[1676]

M. Kaminski
Max-cut and containment relations in graphs
Proceedings of WG 2010, Lecture Notes in Computer Science 6410, 15-26 (2010)

Graphclass: (X42,T2,X205,X206,X207,X208,net)-free

Complement classes

Related classes

Forbidden subgraphs

Inclusions

Map

Minimal superclasses

Maximal subclasses

Speed

Parameters

Problems

Parameter decomposition

Unweighted problems

Weighted problems

Graphclass: (X₄₂,T₂,X₂₀₅,X₂₀₆,X₂₀₇,X₂₀₈,net)-free