Graphclass: linear forest

Definition:

A graph is a linear forest if every connected component is a path .

Complement classes

(co-claw,co-cycle)-free

Forbidden subgraphs

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 linear forest

Minimal superclasses

(2K₃ + e,A,C₅,C₆,E,H,K_3,3-e,R,X₁₆₈,X₁₇₁,X₁₈,X₄₅,X₅,X₅₈,X₈₄,X₉₅,A,C₆,E,H,R,X₁₆₈,X₁₇₁,X₁₈,X₄₅,X₅,X₅₈,X₈₄,X₉₅,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free [from the set of forbidden subgraphs] (known proper)
(6,3) (known proper)
AC (known proper)
(C₄,C₅,C₆,C₇,C₈,H,K_1,4,X₈₅,triangle)-free [from the set of forbidden subgraphs] (known proper)
(C₄,C₅,C₆,C₇,C₈,H,X₈₅,triangle)-free ∩ K_1,4-free (known proper)
(C₄,C₅,C₆,C₇,C₈,XC₁₁,claw,diamond)-free [from the set of forbidden subgraphs] (known proper)
(C₄,K₄,claw,diamond)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4,S₃,claw,net)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4,claw,gem)-free [from the set of forbidden subgraphs] (known proper)
(S₃,claw,net)-free ∩ chordal (known proper)
(T₂,cycle)-free [from the set of forbidden subgraphs] (known proper)
astral triple-free (known proper)
binary tree ∩ partial grid (possibly equal)
bipartite ∩ claw-free (known proper)
caterpillar (known proper)
chordal ∩ domino (known proper)
chordal ∩ unit circular arc (known proper)
(claw,odd-cycle)-free [from the set of forbidden subgraphs] (known proper)
claw-free ∩ interval (known proper)
clique graphs of interval (known proper)
indifference (known proper)
line graphs of acyclic multigraphs (known proper)
linear interval (known proper)
proper interval (known proper)
unit interval (known proper)

Maximal subclasses

(P₃,triangle)-free [from the set of forbidden subgraphs] (known proper)
maximum degree 1 (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)}$ )

factorial

at most factorial From bounded cliquewidth, maximum degree or degeneracy.
at least constant on K₂-free

[1785]

V.E. Alekseev
On lower layers of a lattice of hereditary classes of graphs
Diskretn. Anal. Issled. Oper. Ser. 1 4:1 3-12 (1997)

[1786]

E.R. Scheinerman, J. Zito
On the size of hereditary classes of graphs
J. Combin. Th. B Vol. 61 No.1 16-39 (1994)

[1787]

J. Balogh, B. Bollobas, D. Weinreich
The speed of hereditary properties of graphs
J. Combin. Th. B Vol. 79 No.2 131-156 (2000)

at least factorial on (P₃,triangle)-free

[1785]

V.E. Alekseev
On lower layers of a lattice of hereditary classes of graphs
Diskretn. Anal. Issled. Oper. Ser. 1 4:1 3-12 (1997)

[1786]

E.R. Scheinerman, J. Zito
On the size of hereditary classes of graphs
J. Combin. Th. B Vol. 61 No.1 16-39 (1994)

[1787]

J. Balogh, B. Bollobas, D. Weinreich
The speed of hereditary properties of graphs
J. Combin. Th. B Vol. 79 No.2 131-156 (2000)

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.

Bounded

Bounded from book thickness
Bounded from branchwidth
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from genus
Bounded from maximum degree
Bounded from pathwidth
Bounded from treewidth

Bounded on apex

[1755]

J. Nesetril, P. Ossona de Mendez
Colorings and homomorphisms of minor closed classes
Discrete and Comput. Geometry 25, The Goodman-Pollack Festschrift 651-664 (2003)

Bounded on planar

[1755]

J. Nesetril, P. Ossona de Mendez
Colorings and homomorphisms of minor closed classes
Discrete and Comput. Geometry 25, The Goodman-Pollack Festschrift 651-664 (2003)

Bounded on treewidth 5

[1755]

J. Nesetril, P. Ossona de Mendez
Colorings and homomorphisms of minor closed classes
Discrete and Comput. Geometry 25, The Goodman-Pollack Festschrift 651-664 (2003)

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}\}$.

Unknown to ISGCI

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$.

Bounded

Bounded from branchwidth
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from genus
Bounded from pathwidth
Bounded from treewidth

Bounded on apex

[1830]

(no preview available)

Bounded on book thickness 2 [by definition]
Bounded on planar

[1777]

M. Yannakakis
Embedding planar graph in four pages
Journal of Computer and System Sciences 38 36-67 (1989)

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.

Bounded

Bounded from branchwidth
Bounded from cliquewidth
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from pathwidth
Bounded from rankwidth
Bounded from treewidth

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$.

Bounded

Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from pathwidth
Bounded 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.

Unknown to ISGCI

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.

Bounded

Bounded from acyclic chromatic number
Bounded from book thickness
Bounded from branchwidth
Bounded from degeneracy
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from genus
Bounded from maximum degree
Bounded from pathwidth
Bounded from treewidth

Bounded on 4-colorable [by definition]
Bounded on 5-colorable [by definition]
Bounded on 6-colorable [by definition]
Bounded on bipartite [by definition]
Bounded on tripartite [by definition]

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$.

Bounded

Bounded from booleanwidth
Bounded from branchwidth
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from pathwidth
Bounded from rankwidth
Bounded from treewidth

Bounded on 5-leaf power
Bounded on (A,T₂,odd-cycle)-free

[1183]

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

Bounded on (K₂ ∪ claw,triangle)-free

[1434]

K. Dabrowski, V. Lozin, R. Raman, B. Ries
Colouring vertices of triangle-free graphs
Proceedings of the 36th International Workshop on Graph-Theoretic Concepts in Computer Science WG 2010, LNCS 6410, 184-195 (2010)

Bounded on (P,P,co-fork,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)

Bounded on (X₁₇₂,triangle)-free

[1434]

Bounded on (X₁₇₇,odd-cycle)-free

[1437]

V. Lozin, J. Volz
The clique-width of bipartite graphs in monogenic classes
International J. of Foundations of Comp. Sci. 19 477-494 (2008)

Bounded on (P,fork,gem)-free

[1184]

A. Brandstaedt, H.-O. Le, J.M. Vanherpe
Structure and stability number of (chair, co-P, gem)-free graphs.
Manuscript 2001

[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)

Bounded on (P,fork,house)-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)

[1186]

A. Brandstaedt, R. Mosca
On variations of P_4-sparse graphs.
Manuscript 2001

Bounded on (bull,co-fork,fork)-free

[1124]

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

[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)

Bounded on (bull,fork,gem)-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)

Bounded on (bull,fork,house)-free

[1124]

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

[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)

Bounded on (claw ∪ 3K₁,odd-cycle)-free

[1437]

V. Lozin, J. Volz
The clique-width of bipartite graphs in monogenic classes
International J. of Foundations of Comp. Sci. 19 477-494 (2008)

Bounded on (claw,co-claw)-free

[1126]

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

[1183]

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

Bounded on (claw,paw)-free

[1183]

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

Bounded on cliquewidth 3
Bounded on cliquewidth 4
Bounded on distance-hereditary

[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)

Bounded on (odd-cycle,star_1,2,3,sunlet₄)-free

[1139]

Lozin, Vadim V.
On a generalization of bi-complement reducible graphs.
Proceedings of MFCS 2000, Lect. Notes Comput. Sci. 1893, 528-538 (2000)

Bounded on (odd-cycle,star_1,2,3)-free

[1140]

Lozin, Vadim V.
Bipartite graphs without a skew star
Rutcor Research Report RRR 20-2001

Bounded on probe bipartite distance-hereditary
Bounded on probe distance-hereditary
Bounded on probe ptolemaic
Bounded on tree-cograph

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}$.

Bounded

Bounded from acyclic chromatic number
Bounded from book thickness
Bounded from branchwidth
Bounded from chromatic number
Bounded from degeneracy
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from genus
Bounded from maximum degree
Bounded from pathwidth
Bounded from treewidth

Bounded on bipartite ∪ co-bipartite ∪ split [trivial]
Bounded on (p,q<=2)-colorable

[1866]

(no preview available)

Bounded on probe (2,2)-colorable

[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\}$.

Unknown to ISGCI

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.

Bounded

Bounded from acyclic chromatic number
Bounded from book thickness
Bounded from branchwidth
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from genus
Bounded from maximum degree
Bounded from pathwidth
Bounded from treewidth

Bounded on B₁-CPG
Bounded on CPG
Bounded on apex [by definition]
Bounded on biplanar [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 [by definition]

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.

Bounded

Bounded from distance to linear forest

Bounded on block [by definition]

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 diameter
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 diameter
Unbounded from distance to cograph

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

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.

Bounded

Bounded [by definition]

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.

Bounded

Bounded from distance to linear forest

Bounded on outerplanar [by definition]

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.

Bounded

Bounded on toroidal [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$.

Unknown to ISGCI

maximum clique

[?]

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

Bounded

Bounded from acyclic chromatic number
Bounded from book thickness
Bounded from branchwidth
Bounded from chromatic number
Bounded from degeneracy
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from genus
Bounded from maximum degree
Bounded from pathwidth
Bounded from treewidth

Bounded on K₄-free [by definition]
Bounded on K₆-free [by definition]
Bounded on K₇-free [by definition]
Bounded on triangle-free [by definition]

maximum degree

[?]

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

Bounded

Bounded on maximum degree 7 [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 diameter
Unbounded from maximum induced matching
Unbounded from minimum dominating set

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 diameter

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 diameter
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to cograph
Unbounded from maximum induced matching
Unbounded from tree depth
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 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 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$.

Bounded

Bounded from distance to linear forest

Bounded on caterpillar [trivial]
Bounded on lobster

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$.

Bounded

Bounded from booleanwidth
Bounded from branchwidth
Bounded from cliquewidth
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from pathwidth
Bounded from treewidth

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 diameter

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.

Bounded

Bounded from branchwidth
Bounded from distance to linear forest
Bounded from distance to outerplanar
Bounded from pathwidth

Bounded on (0,3)-colorable ∩ chordal [by definition]
Bounded on partial k-tree, fixed k

[1085]

T.V. Wimer
Linear algorithms on $k$--terminal graphs
Ph. D. Thesis, {\sl Dept. of Computer Science, URI-030, Clemson Univ., Clemson, SC} 1987

[950]

P. Scheffler
The graphs of tree--width $k$ are exactly the partial $k$--trees
manuscript 1986

Bounded on treewidth 2 [by definition]
Bounded on treewidth 3 [by definition]
Bounded on treewidth 4 [by definition]
Bounded on treewidth 5 [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

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.

Polynomial

Polynomial from Bounded booleanwidth

Polynomial on circular permutation
Polynomial on circular trapezoid
Polynomial on convex
Polynomial on d-trapezoid
Polynomial on permutation

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.

Linear

Polynomial from Bounded cliquewidth

Linear on (P,P,co-fork,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)

Linear on (P,fork,gem)-free

[1184]

A. Brandstaedt, H.-O. Le, J.M. Vanherpe
Structure and stability number of (chair, co-P, gem)-free graphs.
Manuscript 2001

[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)

Linear on (P,fork,house)-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)

[1186]

A. Brandstaedt, R. Mosca
On variations of P_4-sparse graphs.
Manuscript 2001

Linear on (bull,co-fork,fork)-free

[1124]

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

[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)

Linear on (bull,fork,gem)-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)

Linear on (bull,fork,house)-free

[1124]

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

[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)

Linear on (claw,co-claw)-free

[1126]

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

[1183]

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

Linear on distance-hereditary

[1177]

Polynomial [$O(V^2E)$] on cliquewidth 3

[1178]

Corneil, Derek G.; Habib, Michel; Lanlignel, Jean-Marc; Reed, Bruce; Rotics, Udi
Polynomial time recognition of clique-width $\leq 3$ graphs (extended abstract).
Gonnet, Gastón H. (ed.) et al., LATIN 2000: Theoretical informatics. 4th Latin American symposium, Punta del Este, Uruguay, April 10-14, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1776, 126-134 (2000)

Polynomial [$O(V^2+VE)$] on (odd-cycle,star_1,2,3,sunlet₄)-free

[1139]

Lozin, Vadim V.
On a generalization of bi-complement reducible graphs.
Proceedings of MFCS 2000, Lect. Notes Comput. Sci. 1893, 528-538 (2000)

Polynomial [$O(V^2+VE)$] on (odd-cycle,star_1,2,3)-free

[1140]

Lozin, Vadim V.
Bipartite graphs without a skew star
Rutcor Research Report RRR 20-2001

Polynomial on tree-cograph

cutwidth decomposition

[?]

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

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

Linear

Linear on bipartite permutation

[1507]

P. Heggernes, P. van 't Hof, D. Lokshtanov, J. Nederlof
Computing the cutwidth of bipartite permutation graphs in linear time
Proceedings of the 36th international conference on Graph-theoretic concepts in computer science WG 2010 75-87 (2010)

Linear on unit interval

[1510]

P. Heggernes, D. Lokshtanov, R. Mihai, C. Papadopoulos
Cutwidth of split graphs, threshold graphs, and proper interval graphs
Proceedings of WG 2008, LNCS 5344, pp. 218-229 (2008)

[1513]

J. Yuan, S. Zhou
Optimal labelling of unit interval graphs
Appl. Math. J. Chinese Univ. Ser. B (English edition) 10 337-344 (1995)

Polynomial on tree

[1514]

M. Yannakakis
A polynomial algorithm for the min cut linear arrangement of trees
Journal of ACM Vol 32, 950-988 (1985)

treewidth decomposition

[?]

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

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

Linear

Linear from Bounded treewidth

Linear on distance-hereditary

[159]

H. Broersma, E. Dahlhaus, T. Kloks
A linear time algorithm for minimum fill--in and treewidth for distance--hereditary graphs
5th Twente workshop 1997

Linear on permutation

[1418]

D. Meister
Treewidth and minimum fill-in on permutation graphs in linear time
Theoretical Comp. Sci. 411 No. 40-42 3685-3700 (2010)

Linear on tree

[119]

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

Linear on treewidth 2

[119]

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

[120]

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

Linear on treewidth 3

[119]

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

[120]

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

Linear on treewidth 4

[119]

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

[120]

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

Linear on treewidth 5

[119]

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

[120]

H.L. Bodlaender
A linear time algorithm for finding tree-decompositions of small treewidth
SIAM J. Comput. 25 No.6 1305-1317 (1996)

Polynomial on HHD-free

[1420]

H.J. Broersma, E. Dahlhaus, T. Kloks
Algorithms for the treewidth and minimum fill-in of HHD-free graphs
23rd Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'97, Lecture Notes in Comp. Sci. 1335 (1997) 109-117

Polynomial on chordal

[119]

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

Polynomial on chordal bipartite

[119]

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

Polynomial on circle

[119]

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

Polynomial on circular arc

[119]

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

Polynomial on circular permutation

[119]

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

Polynomial on co-comparability graphs of dimension d posets

[675]

T. Kloks, D. Kratsch, J. Spinrad
On treewidth and minimum fill--in of asteroidal triple--free graphs
Theor. Comp. Sci. 175 1997 309--335

Polynomial on d-trapezoid

[675]

T. Kloks, D. Kratsch, J. Spinrad
On treewidth and minimum fill--in of asteroidal triple--free graphs
Theor. Comp. Sci. 175 1997 309--335

Polynomial on d-trapezoid
Polynomial on interval

[119]

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

Polynomial on permutation

[119]

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

Polynomial [$O(V^2)$] on trapezoid

[1417]

H.L. Bodlaender, T. Kloks, D. Kratsch, H. Mueller
Treewidth and minimum fill-in on d-trapezoid graphs
J. Graph Algorithms Appl. 2 1-23 (1998)

Polynomial [$O((V+E) \log V)$] on weak bipolarizable

[1419]

E. Dahlhaus
Minimum fill-in and treewidth on graphs modularly decomposable into chordal graphs
24th Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'98, Lecture Notes in Comp. Sci. 1517 (1998) 351-358

Polynomial on weakly chordal

[1421]

V. Bouchitte, I. Todinca
Treewidth and minimum fill-in of weakly triangulated graphs
Annual symposium on theoretical aspects of computer science STACS 99, Lecture Notes in Comp. Sci. 1563 (1999) 197-206

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.

Linear

Linear from Colourability
Linear from FPT-Linear on cliquewidth and Linear decomposition time
Linear from FPT-Linear on treewidth and Linear decomposition time
Polynomial from Colourability
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT-Linear on cliquewidth and Polynomial decomposition time

Linear on (butterfly,claw)-free

[1663]

M. Kaminski, V. Lozin
Vertex 3-colorability of claw-free graphs
Algorithmic Operations Research Vol.2 15-21 (2007)

Linear on dually chordal

[1505]

A. Leitert
3-Colourability of dually chordal graphs in linear time
Manuscript, 2012

Polynomial [$O(V^4)$] on AT-free

[1439]

J. Stacho
3-colouring of AT-free graphs in polynomial time
21st International Symposium on Algorithms and Computation ISAAC, Lecture Notes in Comp. Sci. LNCS 6507 144-155 (2010)

Polynomial on (X₉₁,claw)-free

[1663]

M. Kaminski, V. Lozin
Vertex 3-colorability of claw-free graphs
Algorithmic Operations Research Vol.2 15-21 (2007)

Polynomial on circular arc

[1438]

M.R. Garey, D.S. Johnson, G.L. Miller, C.H. Papadimitriou
The complexity of coloring circular arcs and chords
SIAM J. on Algebraic and Discrete Methods 1 No.2 216-227 (1980)

Polynomial on odd-hole-free

[1744]

(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.

Linear

Linear from Weighted clique
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT on treewidth and Linear decomposition time
Polynomial from Independent set on the complement
Polynomial from Weighted clique
Polynomial from XP on acyclic chromatic number and Linear decomposition time
Polynomial from XP on chromatic number and Linear decomposition time
Polynomial from XP on degeneracy and Linear decomposition time
Polynomial from XP on genus and Linear decomposition time
Polynomial from XP on maximum clique and Linear decomposition time
Polynomial from XP on maximum degree and Linear decomposition time

Linear on Matula perfect

[221]

V. Chv\'atal, C.T. Ho\`ang, N.V.R. Mahadev, D. de Werra
Four classes of perfectly orderable graphs
J. Graph Theory 11 1987 481--495

Polynomial on 2-track

[1553]

M.C. Francis, D. Goncalves, P. Ochem
The maximum clique problem in multiple interval graphs
Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 57-68 (2012)

[1554]

F. Koenig
Sorting with objectives
Ph.D. thesis, Technische Universitaet Berlin (2009)

Polynomial on B₀-VPG
Polynomial on Helly cactus subtree
Polynomial on biclique separable

[1304]

Eschen, Elaine M.; Hoàng, Chính T.; Petrick, Mark D.T.; Sritharan, R
Disjoint clique cutsets in graphs without long holes
J. Graph Theory 48, No.4, 277-298 (2005)

Polynomial [$O(V \log V)$] on boxicity 2

[604]

H. Imai, T. Asano
Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
J. Algorithms 4 1983 310--323

Polynomial [$O(V log^2 V)$] on circle

[1466]

A. Tiskin
Fast distance multiplication of unit-Monge matrices
Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms SODA 1287-1296 (2010)

Polynomial on circular perfect

[1408]

A. Pecher, A.K. Wagler
Clique and chromatic number of circular-perfect graphs
Proceedings of ISCO 2010 - International Symposium on Combinatorial Optimization, Elec. Notes in Discrete Math 36 199-206 (2010)

Polynomial [$O(V^{2.5}/\log V)$] on generalized split
Polynomial on locally chordal
Polynomial on maximum degree 6 [trivial]
Polynomial on maximum degree 7 [trivial]
Polynomial [$O(V \log V)$] on multitolerance
Polynomial [$O(V \log V)$] on tolerance
Polynomial on unit disk

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.

Linear

Polynomial from Colourability on the complement
Polynomial from XP on booleanwidth and Polynomial decomposition time
Polynomial from XP on branchwidth and Linear decomposition time
Polynomial from XP on cliquewidth and Linear decomposition time
Polynomial from XP on cliquewidth and Polynomial decomposition time
Polynomial from XP on distance to linear forest and Linear decomposition time
Polynomial from XP on distance to outerplanar and Linear decomposition time
Polynomial from XP on pathwidth and Linear decomposition time
Polynomial from XP on rankwidth and Linear decomposition time
Polynomial from XP on treewidth and Linear decomposition time

Linear on circular arc

[1158]

Hsu, Wen-Lian; Tsai, Kuo-Hui
Linear time algorithms on circular-arc graphs.
Inf. Process. Lett. 40, No.3, 123-129 (1991)

Linear on tree

[1641]

(no preview available)

Polynomial [$O(V log^{d-1} V)$] on d-trapezoid
Polynomial [$O(V+E)$] on generalized split

[1798]

E.M. Eschen, X. Wang
Algorithms for unipolar and generalized split graphs
Discrete Applied Math. 162 195-201 (2014)

Polynomial [$O(V log log V)$] on trapezoid

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.

Linear

Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT on treewidth and Linear decomposition time

Linear on (0,3)-colorable
Linear on Matula perfect

[221]

V. Chv\'atal, C.T. Ho\`ang, N.V.R. Mahadev, D. de Werra
Four classes of perfectly orderable graphs
J. Graph Theory 11 1987 481--495

Linear on bipartite [trivial]
Linear on chordal

[453]

M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980

Linear on maximum degree 3

[1446]

(no preview available)

Linear on paw-free ∩ perfect
Polynomial on Helly cactus subtree ∩ perfect

[431]

F. Gavril
Intersection graphs of Helly families of subtrees
Discrete Appl. Math. 66 1996 45--56

Polynomial on (K_1,4,paw)-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)

Polynomial on (K₂ ∪ claw,triangle)-free

[1434]

Polynomial on (X₁₇₂,triangle)-free

[1434]

Polynomial on β-perfect

[771]

S.E. Markosjan, G.S. Gasparian, B. Reed
$\beta$--perfect graphs
J. Comb. Theory (B) 67 1996 1--11

Polynomial on biclique separable

[1304]

Eschen, Elaine M.; Hoàng, Chính T.; Petrick, Mark D.T.; Sritharan, R
Disjoint clique cutsets in graphs without long holes
J. Graph Theory 48, No.4, 277-298 (2005)

Polynomial [$O(V^2)$] on chordal

[1424]

C.T. Hoang
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Discrete Appl. Math. 55 133-143 (1994)

Polynomial on circular arc ∩ perfect

[431]

F. Gavril
Intersection graphs of Helly families of subtrees
Discrete Appl. Math. 66 1996 45--56

Polynomial on circular perfect

[1408]

Polynomial on (claw,paw)-free

[1433]

Polynomial on clique separable

[1424]

C.T. Hoang
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Discrete Appl. Math. 55 133-143 (1994)

Polynomial [$O(V^3)$] on co-comparability

[451]

M.C. Golumbic
The complexity of comparability graph recognition and coloring
Computing 18 1977 199--208

Polynomial [$O(V^2)$] on comparability

[1424]

C.T. Hoang
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
Discrete Appl. Math. 55 133-143 (1994)

Polynomial [$O(V^{2.5}/\log V)$] on generalized split
Polynomial [$O(V \log V)$] on multitolerance

[1497]

G.B. Mertzios
An intersection model for multitolerance graphs: Efficient algorithms and hierarchy
Proc. of 21 annual ACM-SIAM symposium on Discrete algorithms SODA2011 1306-1317 (2011)

Polynomial on perfect

[476]

M. Gr\"otschel, L. Lov\'asz, A. Schrijver
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica 1 169--197, 1981 Corrigendum

Polynomial [$O(VE)$] on perfectly orderable
Polynomial [$O(V \log V)$] on permutation

[453]

M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980

Polynomial on permutation

[1165]

A. Brandstaedt, D. Kratsch
On the restriction of some NP-complete graph problems to permutation graphs.
Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 53-62 (1985)

Polynomial on proper circular arc

[1430]

B. Bhattacharya, P. Hell, J. Huang
A linear algorithm for maximum weight cliques in proper circular arc graphs
SIAM J. Discrete Math. 9 No. 2 274-289 (1996)

Polynomial [$O(V \log V)$] on tolerance
Polynomial [$O(V log log V)$] on trapezoid
Polynomial [$O(V^4E)$] on weakly chordal

[530]

R.B. Hayward, C. Ho\`ang, F. Maffray
Optimizing weakly triangulated graphs
Graphs and Combinatorics 5 339--349, Erratum: 6 (1990) 33--35 1989

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.

Linear

Linear from FPT-Linear on cliquewidth and Linear decomposition time
Linear from FPT-Linear on treewidth and Linear decomposition time
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT-Linear on cliquewidth and Polynomial decomposition time

Linear on chordal ∩ claw-free
Linear on circular arc

[1143]

M.S. Chang
Efficient algorithms for the domination problems on interval and circular-arc graphs.
SIAM J. Comput. 27, No.6, 1671-1694 (1998)

[1158]

Hsu, Wen-Lian; Tsai, Kuo-Hui
Linear time algorithms on circular-arc graphs.
Inf. Process. Lett. 40, No.3, 123-129 (1991)

Linear on distance-hereditary

[1153]

F. Nicolai, T. Szymczak
Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
Networks 37,No.3 117-128 (2001)

Linear on dually chordal

[143]

A. Brandst\"adt, V.D. Chepoi, F.F. Dragan
The algorithmic use of hypertree structure and maximum neighbourhood orderings
Discrete Appl. Math. 82 43--77 1998

[332]

F.F. Dragan, C.F. Prisacaru, V.D. Chepoi
Location problems in graphs and the Helly property (in Russian) (1987)
(appeared partially in Diskretnaja Matematika 4 67--73) 1992

Linear on interval

[1143]

M.S. Chang
Efficient algorithms for the domination problems on interval and circular-arc graphs.
SIAM J. Comput. 27, No.6, 1671-1694 (1998)

Linear [$O(V)$] on permutation

[1147]

M. Farber, J.M. Keil
Domination in permutation graphs
J. Algorithms 6 (1985) 309-321

[1148]

K. Tsai, W.L. Hsu
Fast algorithms for the dominating set problem on permutation graphs
Algorithmica 9 (1993) 601-614

[1149]

C. Rhee, Y.D. Liang, S.K. Dhall, S. Lakshmivarahan
An O(n+m) algorithm for finding a minimum-weight dominating set in a permutation graph
SIAM J. Comput. 25 (1996) 404-419

[1165]

[1342]

H.S. Chao, F.R. Hsu, R.C.T. Lee
An Optimal Algorithm for Finding the Minimum Cardinality Dominating Set on Permutation Graphs
Discrete Appl. Math. 102, No.3 159-173 (2000)

Linear on tree
Polynomial on (A,H,K_3,3,K_3,3-e,T₂,X₁₈,X₄₅,domino,triangle)-free

[1267]

D. Rautenbach, V.E. Zverovich
Perfect graphs of strong domination and independent strong domination
Discrete Math. 226 No.1-3 297-311 (2001)

Polynomial on AT-free

[1152]

D. Kratsch
Domination and total domination in asteroidal triple-free graphs
Discrete Appl. Math. 99 No.1-3, 111-123 (2000)

Polynomial on almost tree (1)

[524]

T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.)
Fundamentals of Domination in Graphs
Marcel Dekker, New York, Basel , Vol. 208 1998

Polynomial on cactus

[524]

T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.)
Fundamentals of Domination in Graphs
Marcel Dekker, New York, Basel , Vol. 208 1998

Polynomial [$O(VE)$] on (claw,net)-free

[1127]

A. Brandstaedt, F. Dragan
On linear and circular structure of (claw, net)-free graph
To appear in Discrete Appl. Math.

Polynomial [$O(n^2 log^5 n)$] on co-bounded tolerance

[1172]

J. Mark Keil, P. Belleville
Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs.
Discrete Appl. Math. 140, No.1-3, 73-89 (2004). [ISSN 0166-218X]

Polynomial on co-comparability

[1150]

D. Kratsch, L. Stewart
Domination on cocomparability graphs
SIAM J. Discrete Math. 6(3) (1993) 400-417

[1151]

H. Breu, D.G. Kirkpatrick
Algorithms for the dominating set and Steiner set problems in cocomparability graphs
Manuscript 1993

Polynomial on co-interval ∪ interval
Polynomial on convex

[1167]

Damaschke, Peter; Müller, Haiko; Kratsch, Dieter
Domination in convex and chordal bipartite graphs.
Inf. Process. Lett. 36, No.5, 231-236 (1990)

Polynomial on directed path

[524]

T.W. Haynes, S.T. Hedetniemi, P.J. Slater (eds.)
Fundamentals of Domination in Graphs
Marcel Dekker, New York, Basel , Vol. 208 1998

Polynomial on k-polygon

[352]

E.S. Elmallah, L.K. Stewart
Independence and domination in polygon graphs
Discrete Appl. Math. 44 1993 65--77

Polynomial on permutation

[1165]

Polynomial on probe interval

[1340]

T. Kloks, C.-S. Liu, S.-L. Peng
Domination and independent domination on probe interval graphs
Proceedings of 23rd Workshop on Combinatorial Mathematics and Computation Theory 93-97 (2006)

Polynomial on strongly chordal

[374]

M. Farber
Domination, independent domination, and duality in strongly chordal graphs.
Discrete Appl. Math. 7 1984 115--130

Polynomial on trapezoid

[1155]

Liang, Y. Daniel
Dominations in trapezoid graphs.
Inf. Process. Lett. 52, No.6, 309-315 (1994)

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.

Linear

Linear from Weighted feedback vertex set
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT on treewidth and Linear decomposition time
Polynomial from Weighted feedback vertex set

Linear on bipartite permutation

[1584]

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

Polynomial [$O(V^8E^2)$] on AT-free

[1581]

Feedback vertex set on AT-free graphs
D. Kratsch, H. Mueller, I. Todinca
Discrete Appl. Math. 156 No. 10 1936-1947 (2008)

Polynomial on chordal

[1574]

P. Festa, P.M. Pardalos, M.G.C. Resende
Feedback set problems
in: D.Z. Du, P.M. Pardalos, Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 209-259 (2000)

Polynomial on chordal ∪ co-chordal
Polynomial on chordal bipartite

[1583]

T. Kloks, C.-H. Liu, S.-H. Poon
Feedback vertex set on chordal bipartite graphs
Manuscript (2012)

Polynomial on circular arc

[995]

J.P. Spinrad
Efficient graph representations
American Mathematical Society, Fields Institute Monograph Series 19 (2003)

Polynomial [$O(V^2E)$] on co-comparability

[1579]

M.S Chang, Y.D. Liang
Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs
Acta Informatica 34 337-346 (1997)

Polynomial [$O(V^4)$] on co-comparability

[1578]

S.R. Coorg, C.P. Rangan
Feedback vertex set on cocomparability graphs
Networks 26 101-111 (1995)

Polynomial on co-interval ∪ interval
Polynomial [$O(V^2E)$] on convex

[1579]

M.S Chang, Y.D. Liang
Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs
Acta Informatica 34 337-346 (1997)

Polynomial on interval

[1574]

P. Festa, P.M. Pardalos, M.G.C. Resende
Feedback set problems
in: D.Z. Du, P.M. Pardalos, Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 209-259 (2000)

Polynomial on leaf power ∪ min leaf power
Polynomial [$O(V^2 log^6 V)$] on maximum degree 3

[1584]

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

Polynomial on maximum degree 3

[1586]

S. Ueno, Y. Kajitani, S. Gotoh
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
Discrete Math. 72 No.1-3 355-360 (1988)

Polynomial [$O(VE)$] on permutation

[1576]

Y.D. Liang
On the feedback vertex set problem in permutation graphs
Information Proc. Lett. 52 123-129 (1994)

Polynomial [$O(VE^2)$] on permutation

[1165]

Polynomial [$O(V^6)$] on permutation

[1165]

Polynomial [$O(VE)$] on trapezoid

[1576]

Y.D. Liang
On the feedback vertex set problem in permutation graphs
Information Proc. Lett. 52 123-129 (1994)

Graph isomorphism

[?]

Input: Graphs G and H in this class

Output: True iff G and H are isomorphic.

Linear

Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on treewidth and Linear decomposition time
Polynomial from Graph isomorphism on the complement
Polynomial from XP on booleanwidth and Polynomial decomposition time
Polynomial from XP on cliquewidth and Linear decomposition time
Polynomial from XP on cliquewidth and Polynomial decomposition time
Polynomial from XP on maximum degree and Linear decomposition time
Polynomial from XP on rankwidth and Linear decomposition time

Linear on Helly circular arc

[1773]

A.R. Curtis, M.C. Lin, R.M. McConnell, Y. Nussbaum, F.J. Soulignac, J.P. Spinrad, J.L. Szwarcfiter
Isomorphism of graph classes related to the circular-ones property
DMTCS 15 No. 1 157-182 (2013)

Linear on concave-round

[1773]

A.R. Curtis, M.C. Lin, R.M. McConnell, Y. Nussbaum, F.J. Soulignac, J.P. Spinrad, J.L. Szwarcfiter
Isomorphism of graph classes related to the circular-ones property
DMTCS 15 No. 1 157-182 (2013)

Linear on interval

[127]

K.S. Booth, G.S. Lueker
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms.
J. Comput. Syst. Sci. 13, 335-379 (1976). [ISSN 0022-0000]

Linear on permutation

[234]

C.J. Colbourn
On testing isomorphism of permutation graphs
Networks 11 1981 13--21

Linear on planar

[1700]

R.A. Wilson
Graphs, colourings and the four-colour theorem
Oxford University Press, London 2002

Linear on proper circular arc

[1646]

M.C. Lin, F. Soulignac, J.L. Szwarcfiter
A simple linear time algorithm for the isomorphism problem on proper circular-arc graphs
LNCS 5124 355-366 (2008)

Linear on proper circular arc

[1773]

A.R. Curtis, M.C. Lin, R.M. McConnell, Y. Nussbaum, F.J. Soulignac, J.P. Spinrad, J.L. Szwarcfiter
Isomorphism of graph classes related to the circular-ones property
DMTCS 15 No. 1 157-182 (2013)

Linear on ptolemaic

[1858]

R. Uehara, Y. Uno
Laminar structure of ptolemaic graphs with applications
Discrete Appl. Math. 157 No.7 1533-1543 (2009)

Linear on tree

[6]

A.V. Aho, J.E. Hopcroft, J.D. Ullman
The design and analysis of computer algorithms
Addison--Wesley, Reading, Mass. 1974

Polynomial on co-interval ∪ interval
Polynomial on genus 0

[1686]

I.S. Filotti, J.N. Mayer
A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus
Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing STOC'80 236-243 (1980)

[1687]

G. Miller
Isomorphism testing for graphs of bounded genus
Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing STOC'80 225-235 (1980)

Polynomial on genus 1

[1686]

[1687]

G. Miller
Isomorphism testing for graphs of bounded genus
Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing STOC'80 225-235 (1980)

Polynomial on partial 2-tree

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Polynomial on partial 3-tree

[1701]

M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Polynomial on proper chordal

[1845]

Ch. Paul, E. Protopapas
Tree-layout based graph classes: proper chordal graphs
International Symposioum on Theoretical Aspects of Computer Science STACS 2024, LIPIcs 289 No.55 1-18 (2024)

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.

Linear

Linear from FPT-Linear on treewidth and Linear decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from XP on booleanwidth and Polynomial decomposition time
Polynomial from XP on cliquewidth and Linear decomposition time
Polynomial from XP on cliquewidth and Polynomial decomposition time
Polynomial from XP on rankwidth and Linear decomposition time

Linear on chordal ∩ claw-free

[1872]

S. Chaplick
Intersection graphs of non-crossing paths
Discrete Math. 346 No.8 (2023)

Linear on (claw,net)-free

[1610]

A. Brandstaedt, F.F. Dragan, E. Koehler
Linear time algorithms for the Hamiltonian problems on (claw,net)-free graphs
SIAM J. Computing 30 1662-1677 (2000)

Linear on convex

[1517]

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

Linear on distance-hereditary

[1534]

R.W. Hung, M.S. Chang
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Theoret. Comput. Sci. 341 411-440 (2005)

[1535]

S.Y. Hsieh, C.W. Ho, T.S. Hsu, M.T. Ko
The Hamiltonian problem on distance-hereditary graphs
Discrete Appl. Math. 153 508-524 (2006)

Linear on interval

[1529]

J.M. Keil
Finding hamiltonian circuits in interval graphs
Information Proc. Lett. 20 201-206 (1985)

Linear on proper interval

[1528]

L. Ibarra
A simple algorithm to find Hamiltonian cycles in proper interval graphs
Information Proc. Lett. 109 Issue 18 1105-1108 (2009)

[1530]

B.S. Panda, S.K. Das
A linear time recognition algorithm for proper interval graphs
Information Proc. Lett. 87 153-161 (2003)

Linear on ptolemaic

[1858]

R. Uehara, Y. Uno
Laminar structure of ptolemaic graphs with applications
Discrete Appl. Math. 157 No.7 1533-1543 (2009)

Polynomial on bipartite permutation

[1165]

Polynomial [$O(V \Delta(G))$] on circular arc

[1536]

R.-W. Hung, M.-S. Chang, C.-H. Laio
The Hamiltonian cycle problem on circular-arc graphs
Proc. of the International MultiConference of Engineers and Computer Scientists IMECS 2009

Polynomial [$O(V^2 \log V)$] on circular arc

[1527]

W.K. Shih, T.C. Chen, W.L. Hsu
An O(n^2 log n) algorithm for the Hamiltonian cycle problem on circular-arc graphs
SIAM J. Comput. 21 No.6 1026-1046 (1992)

Polynomial on circular convex bipartite

[1245]

Y. Daniel Liang, N. Blum
Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
Inform. Proc. Letters Vol.56 No.4 215-219 (1995)

Polynomial on (claw,net)-free

[344]

D. Duffus, R.J. Gould, M.S. Jacobson
Forbidden subgraphs and the Hamiltonian theme.
The theory and applications of graphs, 4th int. Conf., Kalamazoo/Mich. 1980, 297-316 (1981).

Polynomial on co-comparability

[1524]

J.S. Deogun, G. Steiner
Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
SIAM J. Computing 23 Issue 3 520-552 (1994)

Polynomial [$O(V \log V)$] on interval
Polynomial [$O(V \log V)$] on proper interval

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.

Linear

Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on treewidth and Linear decomposition time
Polynomial from XP on booleanwidth and Polynomial decomposition time
Polynomial from XP on cliquewidth and Linear decomposition time
Polynomial from XP on cliquewidth and Polynomial decomposition time
Polynomial from XP on rankwidth and Linear decomposition time

Linear on chordal ∩ claw-free

[1872]

S. Chaplick
Intersection graphs of non-crossing paths
Discrete Math. 346 No.8 (2023)

Linear on (claw,net)-free

[1610]

A. Brandstaedt, F.F. Dragan, E. Koehler
Linear time algorithms for the Hamiltonian problems on (claw,net)-free graphs
SIAM J. Computing 30 1662-1677 (2000)

Linear on distance-hereditary

[1534]

R.W. Hung, M.S. Chang
Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
Theoret. Comput. Sci. 341 411-440 (2005)

Polynomial on bipartite permutation

[1165]

Polynomial [$O(V^4)$] on circular arc

[1543]

G.B. Mertzios, I. Bezakova
Computing and counting longest paths on circular-arc graphs in polynomial time
Discrete Appl. Math, in press

Polynomial on (claw,net)-free

[344]

D. Duffus, R.J. Gould, M.S. Jacobson
Forbidden subgraphs and the Hamiltonian theme.
The theory and applications of graphs, 4th int. Conf., Kalamazoo/Mich. 1980, 297-316 (1981).

Polynomial on co-comparability

[1524]

J.S. Deogun, G. Steiner
Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
SIAM J. Computing 23 Issue 3 520-552 (1994)

Polynomial [$O(V \log V)$] on interval

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.

Linear

Linear from Weighted independent dominating set
Polynomial from Weighted independent dominating set

Linear on chordal

[1669]

M. Farber
Independent domination in chordal graphs
Operations Research Lett. 1 No.4 134-138 (1982)

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.

Linear

Linear from Weighted independent set
Polynomial from Clique on the complement
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT on treewidth and Linear decomposition time
Polynomial from Weighted independent set

Linear on chordal

[425]

F. Gavril
The intersection graphs of subtrees in trees are exactly the chordal graphs
J. Comb. Theory (B) 16 1974 47--56

[931]

D.J. Rose, R.E. Tarjan, G.S. Lueker
Algorithmic aspects of vertex elimination on graph
SIAM J. Computing 5 1976 266--283

Linear [$O(n)$] on circular arc

[1105]

M.C. Golumbic, P.L Hammer
Stability in circular arc graphs.
J. Algorithms 9 (1988) 56-63

[1106]

W.L. Hsu, J.P. Spinrad
Independent sets in circular arc graphs
J. Algorithms 19 (1995) 145-160

[1158]

Hsu, Wen-Lian; Tsai, Kuo-Hui
Linear time algorithms on circular-arc graphs.
Inf. Process. Lett. 40, No.3, 123-129 (1991)

Linear on co-comparability

[1100]

R.M. McConnell, J.P. Spinrad
Modular decomposition and transitive orientation
Discrete Math. 201 (1999) 189-241

Polynomial on (E,P)-free

[1305]

M.U. Gerber, V.V. Lozin
Robust algorithms for the stable set problem
Graphs and Combin., to appear

Polynomial on E-free ∩ planar

[1665]

V. Lozin, M. Milanic
On the Maximum Independent Set Problem in Subclasses of Planar Graphs
Journal of Graph Algorithms and Applications Vol.14 No.2 269-286 (2010)

Polynomial on EPT

[1019]

R.E. Tarjan
Decomposition by clique separators
Discrete Math. 55 1985 221--232

[1381]

(no preview available)

Polynomial on Gallai

[1081]

S.H. Whitesides
A method for solving certain graph recognition and optimization problems, with applications to perfect graphs
Annals of Discrete Math. 21 1984 281--297

Polynomial on Meyniel

[169]

M. Burlet, J. Fonlupt
Polynomial algorithm to recognize a Meyniel graph
Annals of Discrete Math. 21 1984 225--252

Polynomial on (P,T₂)-free

[1305]

M.U. Gerber, V.V. Lozin
Robust algorithms for the stable set problem
Graphs and Combin., to appear

Polynomial on (P,star_1,2,5)-free

[1349]

V.L. Lozin, M. Milanic
On finding augmenting graphs
Rutcor Research Report 28-2005

Polynomial [$O(V min(d,\alpha))$] on circle

[1465]

N. Nash, D. Gregg
An output sensitive algorithm for computing a maximum independent set of a circle graph
Inform. Process. Lett. 110 No.16 630-634 (2010)

Polynomial [$O(VE)$] on (claw,net)-free

[1127]

A. Brandstaedt, F. Dragan
On linear and circular structure of (claw, net)-free graph
To appear in Discrete Appl. Math.

[515]

P.L. Hammer, N.V.R. Mahadev, D. de Werra
The struction of a graph: application to CN--free graphs
Combinatorica 5 1985 141--147

Polynomial on claw-free

[947]

N. Sbihi
Algorithme de recherche d'un stable de cardinalit\'e maximum dans un graphe sans \'etoile
Discrete Math. 29 1980 53--76

Polynomial on clique separable

[1081]

S.H. Whitesides
A method for solving certain graph recognition and optimization problems, with applications to perfect graphs
Annals of Discrete Math. 21 1984 281--297

Polynomial on co-biclique separable

[1304]

Eschen, Elaine M.; Hoàng, Chính T.; Petrick, Mark D.T.; Sritharan, R
Disjoint clique cutsets in graphs without long holes
J. Graph Theory 48, No.4, 277-298 (2005)

Polynomial on comparability

[453]

M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980

Polynomial [$O(V+E)$] on generalized split

[1798]

E.M. Eschen, X. Wang
Algorithms for unipolar and generalized split graphs
Discrete Applied Math. 162 195-201 (2014)

Polynomial on gridline

[871]

D. Peterson
Gridline graphs: A review in two dimensions and an extension to higher dimensions.
Discrete Appl. Math. 126, No.2-3, 223-239 (2003). [ISSN 0166-218X]

Polynomial [$O(VE)$] on weakly chordal

[1119]

R. Hayward, J. Spinrad. R. Sritharan
Weakly chordal graph algorithms via handles
Proc. of the 11th symposium on Discrete Algorithms 42-49, 2000

[530]

R.B. Hayward, C. Ho\`ang, F. Maffray
Optimizing weakly triangulated graphs
Graphs and Combinatorics 5 339--349, Erratum: 6 (1990) 33--35 1989

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.

Linear

Linear from FPT-Linear on treewidth and Linear decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to block and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from Weighted maximum cut
Polynomial from XP,W-hard on booleanwidth and Polynomial decomposition time
Polynomial from XP,W-hard on cliquewidth and Linear decomposition time
Polynomial from XP,W-hard on cliquewidth and Polynomial decomposition time
Polynomial from XP,W-hard on rankwidth and Linear decomposition time

Linear on bipartite

[1629]

H.L. Bodlaender, K. Jansen
On the complexity of the maximum cut problem
Nordic J. Comput. 7 No.1 14-31 (2000)

[trivial]
Polynomial [$O(V^4)$] on block

[1727]

R. Crowston, M. Jones, M. Mnich
Max-cut parametrized above the Edwards-Erdős bound
Algorithmica Jan. 2014 1-24 (2014)

Polynomial on line

[1678]

V. Guruswami
Maximum cut on line and total graphs
Discrete Appl. Math. 92 217-221 (1999)

Polynomial on planar

[1628]

J. Diaz, M. Karminski
Max-Cut and Max-Bisection are NP-hard on unit disk graphs
Theo. Comp. Sci 377 271-276 (2007)

Polynomial on proper interval

[1855]

A. Boyacı, T. Ekim, M. Shalom
A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
Information Proc. Letters 121 29-33 (2017)

Monopolarity

[?]

Input: A graph G in this class.

Output: True iff G is monopolar.

Linear

Linear on chordal

[1767]

T. Ekim, P. Hell, J. Stacho, D. de Werra
Polarity of chordal graphs
Discrete Applied Mathematics 156 No. 13 2469-2479 (2008)

Linear on line

[1770]

R. Churchley, J. Huang
Line-polar graphs: Characterization and recognition
SIAM J. Discrete Math. 25 1269-1284 (2011)

Linear on monopolar [trivial]
Polynomial [$O(V^4)$] on (5-pan,T₂,X₁₇₂)-free

[1764]

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

Polynomial on bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
Polynomial on bipartite ∪ co-bipartite ∪ split
Polynomial [$O(V^3)$] on claw-free

[1768]

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

Polynomial on hole-free

[1764]

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

Polynomial [$O(VE)$] on permutation

[1769]

T. Ekim, P. Heggernes, D. Meister
Polar permutation graphs are polynomial-time recognisable
European J. Combin. 34 No.3 576-592 (2013)

Polarity

[?]

Input: A graph G in this class.

Output: True iff G is polar.

Linear

Polynomial from XP on booleanwidth and Polynomial decomposition time
Polynomial from XP on branchwidth and Linear decomposition time
Polynomial from XP on cliquewidth and Linear decomposition time
Polynomial from XP on cliquewidth and Polynomial decomposition time
Polynomial from XP on distance to linear forest and Linear decomposition time
Polynomial from XP on distance to outerplanar and Linear decomposition time
Polynomial from XP on pathwidth and Linear decomposition time
Polynomial from XP on rankwidth and Linear decomposition time
Polynomial from XP on treewidth and Linear decomposition time

Linear on line

[1770]

R. Churchley, J. Huang
Line-polar graphs: Characterization and recognition
SIAM J. Discrete Math. 25 1269-1284 (2011)

Linear on polar [trivial]
Polynomial on (5-pan,T₂,X₁₇₂)-free ∩ planar

[1764]

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

Polynomial on bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
Polynomial on chordal

[1767]

T. Ekim, P. Hell, J. Stacho, D. de Werra
Polarity of chordal graphs
Discrete Applied Mathematics 156 No. 13 2469-2479 (2008)

Polynomial on chordal ∪ co-chordal
Polynomial on co-interval ∪ interval
Polynomial on hole-free ∩ planar

[1764]

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

Polynomial on leaf power ∪ min leaf power
Polynomial [$O(VE^2)$] on permutation

[1769]

T. Ekim, P. Heggernes, D. Meister
Polar permutation graphs are polynomial-time recognisable
European J. Combin. 34 No.3 576-592 (2013)

Recognition

[?]

Input: A graph G.

Output: True iff G is in this graph class.

Polynomial

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.

Linear

Linear from FPT-Linear on treewidth and Linear decomposition time
Polynomial from FPT on acyclic chromatic number and Linear decomposition time
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on degeneracy and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on genus and Linear decomposition time
Polynomial from FPT on maximum degree and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from Weighted independent set on the complement
Polynomial from XP on chromatic number and Linear decomposition time
Polynomial from XP on maximum clique and Linear decomposition time

Linear on comparability

[453]

M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980

Linear on planar

[1869]

C.H. Papadimitriou, M. Yannakakis
The clique problem for planar graphs
Information Proc. Letters 13 131-133 (1981)

Linear on proper circular arc

[1430]

B. Bhattacharya, P. Hell, J. Huang
A linear algorithm for maximum weight cliques in proper circular arc graphs
SIAM J. Discrete Math. 9 No. 2 274-289 (1996)

Polynomial on 4-colorable [trivial]
Polynomial on 5-colorable [trivial]
Polynomial on 6-colorable [trivial]
Polynomial [$O(V^2 E)$] on C₄-free ∩ odd-signable

[1476]

M.V. da Silva, K. Vuskovic
Triangulated neighborhoods in even-hole-free graphs
Discrete Math. 307 1065-1073 (2007)

Polynomial on (K_3,3,K₅)-minor-free
Polynomial on (W₄,claw)-free
Polynomial on alternation

[1598]

M.M. Halldorson, S. Kitaev, A. Pyatkin
Alternation graphs
Proceedings of WG 2011, Lecture Notes in Computer Science 6986, 191-202 (2011)

Polynomial on bipartite ∪ co-bipartite ∪ split
Polynomial [$O(V^2 + E \log \log V)$] on circle

[1429]

W.-L. Hsu
Maximum weight clique algorithms for circular-arc graphs and circle graphs
SIAM J. Computing 14 No.1 224-231 (1985)

Polynomial [$O(V^2 \log V)$] on circle-trapezoid
Polynomial [$O(VE)$] on circular arc

[1429]

W.-L. Hsu
Maximum weight clique algorithms for circular-arc graphs and circle graphs
SIAM J. Computing 14 No.1 224-231 (1985)

[453]

M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980

Polynomial on co-comparability ∪ comparability
Polynomial on interval filament

[1159]

F. Gavril
Maximum weight independent sets and cliques in intersection graphs of filaments.
Information Processing Letters 73(5-6) 181-188 (2000)

Polynomial on max-tolerance

[1481]

M. Kaufmann, J. Kratochvil, K.A. Lehmann, A.R. Subramanian
Max-tolerance graphs as intersection graphs: cliques, cycles and recognition
Proc. of 17th annual ACM-SIAM symposium on Discrete algorithms SODA'06 832-841 (2006)

Polynomial on maximal clique irreducible

[1642]

(no preview available)

Polynomial on monopolar

[1832]

M. Barbato, D. Bezzi
Monopolar graphs: Complexity of computing classical graph parameters
Discrete Appl. Math. 291 277-285 (2021)

Polynomial [$O(VE)$] on perfectly orderable
Polynomial [$O(VE)$] on split-neighbourhood

[759]

F. Maffray, M. Preissmann
Split--neighbourhood graphs and the strong perfect graph conjecture
J. Comb. Theory (B) 63 1995 294--309

Polynomial [$O(V log log V)$] on trapezoid

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.

Linear

Linear from FPT-Linear on cliquewidth and Linear decomposition time
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT on treewidth and Linear decomposition time
Polynomial from FPT-Linear on cliquewidth and Polynomial decomposition time

Linear on interval

[1577]

C.L. Lu, C.Y. Tang
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
Information Proc. Lett. 61 107-111 (1997)

Polynomial on circle

[1585]

F. Gavril
Minimum weight feedback vertex sets in circle graphs
Information Proc. Lett. 107 No.1 1-6 (2008)

Polynomial [$O(V^{2n+5})$] on circle-n-gon, fixed n
Polynomial on co-interval ∪ interval

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.

Linear

[374]

M. Farber
Domination, independent domination, and duality in strongly chordal graphs.
Discrete Appl. Math. 7 1984 115--130

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.

Linear

Linear from FPT-Linear on cliquewidth and Linear decomposition time
Linear from FPT-Linear on treewidth and Linear decomposition time
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on branchwidth and Linear decomposition time
Polynomial from FPT on distance to linear forest and Linear decomposition time
Polynomial from FPT on distance to outerplanar and Linear decomposition time
Polynomial from FPT on pathwidth and Linear decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT-Linear on cliquewidth and Polynomial decomposition time
Polynomial from Weighted clique on the complement

Linear on AT-free ∩ claw-free

[1157]

H. Hempel, D. Kratsch
On claw-free asteroidal triple-free graphs
Discrete Appl. Math. 121, No.1-3, 155-180 (2002)

Linear on chordal

[1166]

A. Frank
Some polynomial algorithms for certain graphs and hypergraphs.
Proc. 5th Br. comb. Conf., Aberdeen 1975, Congr. Numer. XV, 211-226 (1976).

Linear on (claw,co-claw)-free

[1126]

A. Brandstaedt, S. Mahfud
Maximum weight stable set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
Information Processing Letters 84 (2002) 251-259

Linear on distance-hereditary
Linear on permutation

[1164]

V. Kamakoti, C. Pandu Rangan
Efficient Transitive Reduction on Permutation Graphs and its Applications.
CSI JL on Computer Science and Informatics, Vol. 23, No. 3, pp. 52 - 59 (1993)

Polynomial [$O(V + V \Delta(G))$] on 2-thin
Polynomial [$O(V^4)$] on AT-free

[160]

H. Broersma, T. Kloks, D. Kratsch, H. M\"uller
Independent sets in asteroidal triple-free graphs
SIAM J. Discrete Math. 12, No.2, 276-287 (1999)

Polynomial [$O(V^5E^3)$] on Berge ∩ bull-free

[1278]

C.M.H. de Figueiredo, F. Maffray
Optimizing bull-free perfect graphs
SIAM J. Discrete Math. Vol.18 No.2 226-240 (2004)

Polynomial on (C₄,C₅,T₂)-free

[1108]

V.E. Alekseev
On the local restrictions effect on the complexity of finding the graph independence number
Combinatorial-algebraic methods in applied mathematics Gorkiy Univ. Press, Gorkiy (1983) 3-13 (in Russian)

Polynomial on K₂ ∪ claw-free

[1290]

V. Lozin, R. Mosca
Independent sets and extensions of 2K_2-free graphs
Discrete Appl. Math. 146 74-80 (2005)

Polynomial on (K_2,3,P,hole)-free

[1107]

N.V.R. Mahadev
Vertex deletion and stability number
Research report ORWP 90/2 Dept. of Mathematics, Swiss Fed.Inst. of Technology 1990

Polynomial on (P,butterfly,fork,gem)-free

[1104]

V.V. Lozin
Conic reduction of graphs for the stable set problem.
Discrete Math. 222 (2000) 199-211

Polynomial [$O(VE)$] on (P,fork)-free

[1125]

A. Brandstaedt, V.B. Le, H.N. de Ridder
Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes.
Universitaet Rostock, Fachbereich Informatik, Preprint CS-14-01

Polynomial on bipartite
Polynomial [$O(VE)$] on (bull,fork)-free

[1124]

A. Brandstaedt, C.T. Hoang, V.B. Le
Stability number of bull- and chair-free graphs revisited
to appear in Discrete Appl. Math.

[307]

C. De Simone, A. Sassano
Stability number of bull-- and chair--free graphs
Discrete Appl. Math. 41 1993 121--129

Polynomial [$O(V^2)$] on circle

[1121]

A. Apostolico, M.J. Atallah, S.E. Hambrusch
New clique and independent set algorithms for circle graphs.
Discrete Appl. Math 36 (1992) 1-24 Erratum: Discrete Appl. Math 41 (1993) 179-180

Polynomial [$O(V^2)$] on circle-trapezoid
Polynomial [$O(ln)$] on circular arc
Polynomial [$O(V^2 \log \log V)$] on circular trapezoid
Polynomial on claw-free

[783]

G.J. Minty
On maximal independent sets of vertices in claw--free graphs
J. Comb. Theory (B) 28 1980 284--304

Polynomial on (co-fork,hole)-free

[1494]

A. Brandstaedt, V. Giakoumakis
Maximum Weight Independent Sets in Hole- and Co-Chair-Free Graphs
Inform. Proc. Lett. 112 67-71 (2012)

Polynomial [$O(V log^{d-1} V)$] on d-trapezoid
Polynomial on fork-free

[1099]

V.E. Alekseev
A polynomial algorithm for finding maximum independent sets in fork-free graphs
Discrete Ann. Operation Res., Ser. 1 6 (1999) 3-19 (in Russian)

Polynomial on interval filament

[1159]

F. Gavril
Maximum weight independent sets and cliques in intersection graphs of filaments.
Information Processing Letters 73(5-6) 181-188 (2000)

Polynomial [$O(E + V \log V)$] on multitolerance

[1497]

G.B. Mertzios
An intersection model for multitolerance graphs: Efficient algorithms and hierarchy
Proc. of 21 annual ACM-SIAM symposium on Discrete algorithms SODA2011 1306-1317 (2011)

Polynomial on (n+4)-pan-free

[1447]

A. Brandstaedt, V.V. Lozin, R. Mosca
Independent sets of maximum weight in apple-free graphs
SIAM J. Discrete Math. Vol.24 No.1 239-254 (2010)

Polynomial on nearly bipartite
Polynomial [$O(n^{6p+2})$] on (p,q<=2)-colorable

[1116]

V.E. Alekseev, V.V. Lozin
Independent sets of maximum weight in (p,q)-colorable graphs
Rutcor Research Report 12-2002

Polynomial on parity

[170]

M. Burlet, J.P. Uhry
Parity graphs
Annals of Discrete Math. 21 1984 253--277

Polynomial on perfect

[476]

M. Gr\"otschel, L. Lov\'asz, A. Schrijver
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica 1 169--197, 1981 Corrigendum

Polynomial on subtree overlap

[1123]

E. Cenek, L. Stewart
Maximum independent set and maximum clique algorithms for overlap graphs
Discrete Appl. Math. 131, No.1 77-91 (2003)

Polynomial [$O(V \log V)$] on tolerance
Polynomial [$O(V^2)$] on tolerance

[1498]

G.B. Mertzios, I. Sau, S. Zaks
A new intersection model and improved algorithms for tolerance graphs
SIAM J. on Discrete Math. 23(4) 1800-1813 (2009)

Polynomial [$O(V \log \log V)$] on trapezoid
Polynomial [$O(V^4)$] on weakly chordal

[997]

J.P. Spinrad, R. Sritharan
Algorithms for weakly triangulated graphs
Discrete Appl. Math. 59 1995 181--191

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.

Polynomial

Polynomial [$O(V^{3/2}\log V)$] on planar

[1658]

W.-k. Shih, S. Wu, Y.S. Kuo
Unifying Maximum Cut and Minimum Cut of a Planar Graph
IEEE Transactions on Computer 39 No.5 694-697 (1990)

Graphclass: linear forest

Complement classes

Related classes

Forbidden subgraphs

Inclusions

Map

Minimal superclasses

Maximal subclasses

Speed

Parameters

Problems

Parameter decomposition

Unweighted problems

Weighted problems