Graphclass: (3K₁,paw)-free

Complement classes

(co-paw,triangle)-free

Forbidden subgraphs

3K₁3K_1 pawpaw

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 (3K_1,paw)--free

Minimal superclasses

(3K₁,2P₃)-free [from the set of forbidden subgraphs] (known proper)
(3K₁,K₂ ∪ claw)-free [from the set of forbidden subgraphs] (known proper)
(3K₁,P₂ ∪ P₄)-free [from the set of forbidden subgraphs] (known proper)
(3K₁,co-fork)-free [from the set of forbidden subgraphs] (known proper)
(3K₁,house)-free [from the set of forbidden subgraphs] (known proper)
(3K₂,P,co-gem,house)-free [from the set of forbidden subgraphs] (known proper)
(4K₁,gem)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4 ∪ K₁,K_2,3,T₂,X₉₀,domino,paw,twin-C₅)-free [from the set of forbidden subgraphs] (known proper)
(C_n+4 ∪ K₁,S₃ ∪ K₁,X₄₂,T₂,X₂,X₃,odd-cycle ∪ K₁,even anti-hole,net)-free [from the set of forbidden subgraphs] (known proper)
(C_n+3 ∪ K₁,co-diamond,co-paw)-free [from the set of forbidden subgraphs] (known proper)
circular arc ∩ paw-free (known proper)
circular interval (known proper)
(claw,paw)-free [from the set of forbidden subgraphs] (known proper)
(co-paw,paw)-free [from the set of forbidden subgraphs] (known proper)
proper circular arc (known proper)

Maximal subclasses

(3K₁,P₃)-free [from the set of forbidden subgraphs] (known proper)
(3K₁,P₃)-free [from the set of forbidden subgraphs] (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 factorial on (3K₁,P₃)-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.

Unbounded

Unbounded from chromatic number
Unbounded from degeneracy
Unbounded from maximum clique

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 acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from carvingwidth
Unbounded from chromatic number
Unbounded from cutwidth
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from maximum degree
Unbounded from pathwidth
Unbounded from treewidth

Unbounded on complete [by definition]

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

Bounded

Bounded from booleanwidth on the complement
Bounded from cliquewidth
Bounded from rankwidth

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 acyclic chromatic number
Unbounded from book thickness
Unbounded from chromatic number
Unbounded from degeneracy
Unbounded from maximum clique
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

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 maximum clique

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 cliquewidth on the complement
Bounded from rankwidth

Bounded on (9,6)

[488]

A. Gy\'arf\'as, D. Kratsch, J. Lehel, F. Maffray
Minimal non--neighbourhood--perfect graphs
J. Graph Theory 21 55--66 1996

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 P₄-tidy

[1175]

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

Bounded on (P₅,bull,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)

[1187]

J.-L. Fouquet
A decomposition for a class of (P_5, \overline{P_5})-free graphs.
Discrete Math. 121 (1993) 19-30

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)

[402]

J.L. Fouquet, V. Giakoumakis
On semi--$P_4$--sparse graphs
Discrete Math. 165/166 1997 277--300

Bounded on (P₅,gem)-free

[1171]

A. Brandstaedt, D. Kratsch
On the structure of (P_5,gem)-free graphs.
Manuscript 2002

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

[1189]

A. Brandstaedt, H.-O. Le, R. Mosca
Chordal co-gem-free graphs have bounded clique-width
Manuscript 2002

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,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 4
Bounded on (co-gem,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)

[1188]

A. Brandstaedt, H.-O. Le, R. Mosca
(gem, co-gem)-free graphs have bounded clique-width
Manuscript 2002

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

Bounded on partner-limited

[1179]

J.M. Vanherpe
Clique-width of partner-limited graphs.
International Conference of Graph Theory, Marseille 2000

Bounded on (q, q-3), fixed q>= 7

[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

Bounded on semi-P₄-sparse

[1186]

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

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 minimum clique cover

Bounded on (p,q<=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\}$.

Unbounded

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from carvingwidth
Unbounded from chromatic number
Unbounded from degeneracy
Unbounded from maximum clique
Unbounded from maximum degree
Unbounded from pathwidth
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 chromatic number
Unbounded from maximum clique

diameter

[?]

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

Bounded

Bounded from maximum independent set
Bounded from maximum induced matching
Bounded from minimum clique cover
Bounded from minimum dominating set

Bounded on P₇-free [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.

Unbounded

Unbounded on (3K₁,P₃)-free

[1827]

(no preview available)

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 distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster

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 distance to block

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

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 .

Unknown to ISGCI

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

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

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 degeneracy
Unbounded from maximum clique

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 acyclic chromatic number
Unbounded from bandwidth
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from carvingwidth
Unbounded from chromatic 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 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]

maximum degree

[?]

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

Unbounded

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

Unbounded on complete [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$.

Bounded

Bounded from maximum clique on the complement
Bounded from minimum clique cover

Bounded on 3K₁-free [by definition]
Bounded on 4K₁-free [by definition]
Bounded on 5K₁-free [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$.

Bounded

Bounded from maximum independent set
Bounded from minimum clique cover

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 acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from degeneracy
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to linear forest
Unbounded from distance to outerplanar
Unbounded from maximum clique
Unbounded from pathwidth
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.

Bounded

Bounded from chromatic number on the complement

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

Bounded

Bounded from maximum independent set
Bounded from minimum clique cover

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

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 cliquewidth
Bounded from rankwidth on the complement

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

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

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 acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from chromatic number
Unbounded from degeneracy
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to linear forest
Unbounded from distance to outerplanar
Unbounded from maximum clique
Unbounded from maximum matching
Unbounded from pathwidth
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.

Polynomial

Polynomial from Bounded booleanwidth

Polynomial on circular trapezoid

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
Polynomial from cliquewidth decomposition on the complement

Linear on (9,6)

[488]

A. Gy\'arf\'as, D. Kratsch, J. Lehel, F. Maffray
Minimal non--neighbourhood--perfect graphs
J. Graph Theory 21 55--66 1996

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₄-tidy

[1175]

B. Courcelle, J.A. Makowsky, U. Rotics
Linear time optimization problems on graphs of bounded clique width.
Theory of Computing Systems 33 (2000) 125-150

Linear on (P₅,bull,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)

[1187]

J.-L. Fouquet
A decomposition for a class of (P_5, \overline{P_5})-free graphs.
Discrete Math. 121 (1993) 19-30

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)

[402]

J.L. Fouquet, V. Giakoumakis
On semi--$P_4$--sparse graphs
Discrete Math. 165/166 1997 277--300

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 (co-paw,paw)-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 partner-limited

[1179]

J.M. Vanherpe
Clique-width of partner-limited graphs.
International Conference of Graph Theory, Marseille 2000

Linear on (q, q-3), fixed q>= 7

[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

Linear on semi-P₄-sparse

[1186]

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

cutwidth decomposition

[?]

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

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

Unknown to ISGCI

treewidth decomposition

[?]

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

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

Polynomial

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

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 FPT-Linear on cliquewidth and Linear decomposition time
Linear from FPT-Linear on maximum independent set and Linear decomposition time
Polynomial from Colourability
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on minimum clique cover 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)

Polynomial on 2P₃-free

[1431]

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

Polynomial on 4K₁-free

[1431]

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

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 P₂ ∪ P₄-free

[1431]

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

Polynomial on P₅-free

[1242]

B. Randerath, I. Schiermeyer, M. Tewes
Three-colourability and forbidden subgraphs II: polynomial algorithms
Discrete Math. 251 137-212 (2002)

[1441]

C.T. Hoang, M. Kaminski, V. Lozin, J. Sawada, X. Shu
Deciding k-colorability of P_5-free graphs in polynomial time
Algorithmica Vol.57 No.1 74-81 (2010)

Polynomial on P₆-free

[1243]

B. Randerath, I. Schiermeyer
3-colorability in P for P_6-free graphs
Discrete Appl. Math. 136 299-313 (2004)

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 co-gem-free

[1431]

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

Polynomial on nP₃-free, fixed n

[1431]

H. Broersma, P.A. Golovach, D. Paulusma, J. Song
Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time
Manuscript (2010)

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 cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from Independent set on the complement
Polynomial from Weighted clique

Polynomial on b-perfect

[1478]

C.T. Hoang, F. Maffray, M. Mechebbek
A characterization of b-perfect graphs
Manuscript, 2010

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)

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

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.

Polynomial

Polynomial from Clique cover on the complement
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time

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 b-perfect

[1478]

C.T. Hoang, F. Maffray, M. Mechebbek
A characterization of b-perfect graphs
Manuscript, 2010

Polynomial on (claw,paw)-free

[1433]

Polynomial on co-paw-free

[1433]

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)

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
Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from FPT-Linear on cliquewidth and Polynomial decomposition time
Polynomial from XP on maximum independent set and Linear decomposition time
Polynomial from XP on minimum clique cover and Linear decomposition time
Polynomial from XP on minimum dominating set and Linear decomposition time

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)

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

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 cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from Weighted feedback vertex set
Polynomial from XP on maximum independent set and Linear decomposition time
Polynomial from XP on minimum clique cover and Linear decomposition time

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 circular arc

[995]

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

Graph isomorphism

[?]

Input: Graphs G and H in this class

Output: True iff G and H are isomorphic.

Linear

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 rankwidth and Linear decomposition time

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

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

Polynomial from FPT on maximum independent set and Linear decomposition time
Polynomial from FPT on minimum clique cover 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 (P₆,claw)-free

[1694]

(no preview available)

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)

Polynomial on 3K₁-free

[1861]

N. Jedličková, J. Kratochvil
On the structure of Hamiltonian graphs with small independence number
Combinatorial Algorithms. IWOCA 2024. LNCS 14764 180-192 (2024)

Polynomial on 4K₁-free

[1861]

N. Jedličková, J. Kratochvil
On the structure of Hamiltonian graphs with small independence number
Combinatorial Algorithms. IWOCA 2024. LNCS 14764 180-192 (2024)

Polynomial on 5K₁-free

[1861]

N. Jedličková, J. Kratochvil
On the structure of Hamiltonian graphs with small independence number
Combinatorial Algorithms. IWOCA 2024. LNCS 14764 180-192 (2024)

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

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

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

Polynomial on 3K₁-free

[1861]

N. Jedličková, J. Kratochvil
On the structure of Hamiltonian graphs with small independence number
Combinatorial Algorithms. IWOCA 2024. LNCS 14764 180-192 (2024)

Polynomial on 4K₁-free

[1861]

N. Jedličková, J. Kratochvil
On the structure of Hamiltonian graphs with small independence number
Combinatorial Algorithms. IWOCA 2024. LNCS 14764 180-192 (2024)

Polynomial on 5K₁-free

[1861]

N. Jedličková, J. Kratochvil
On the structure of Hamiltonian graphs with small independence number
Combinatorial Algorithms. IWOCA 2024. LNCS 14764 180-192 (2024)

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

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

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 cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from Weighted independent set
Polynomial from XP on maximum independent set and Linear decomposition time
Polynomial from XP on minimum clique cover and Linear decomposition time

Linear on P₄-tidy

[440]

V. Giakoumakis, F. Roussel, H. Thuillier
On $P_4$--tidy graphs
Discrete Math. and Theor. Comp. Sci. 1 1997 17--41

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 extended P₄-laden

[438]

V. Giakoumakis
$P_4$--laden graphs: a new class of brittle graphs
Inf. Proc. Letters 60 1996 29--36

Linear on partner-limited

[1180]

F. Roussel, I. Rusu, H. Thuillier
On graphs with limited number of P_4-partners.
International Journal of Foundations of Computer Science, 1o 103-121 (1999)

Polynomial on (C₆,K_3,3+e,P,P₇,X₃₇,X₄₁)-free

[1346]

N.V.R. Mahadev, B.A. Reed
A note on vertex orders for stability number
J. Graph Theory 30 113-120 (1999)

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 (K_2,3,P,P₅)-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

[1346]

N.V.R. Mahadev, B.A. Reed
A note on vertex orders for stability number
J. Graph Theory 30 113-120 (1999)

Polynomial [$O(nm)$] on (K_3,3-e,P₅,X₉₈)-free

[1117]

A. Brandstaedt, V.V. Lozin
A note on \alpha-redundant vertices in graphs.
Discrete Appl. Math. 108 (2001) 301-308

Polynomial [$O(V^{5})$] on (K_3,3-e,P₅,X₉₉)-free

[1307]

M.U. Gerber, A. Hertz, D. Schindl
P_5-free graphs and the maximum stable set problem
Discrete Appl. Math. 132 109-119 (2004)

Polynomial on (K_3,3-e,P₅)-free

[1246]

V. Alekseev, P. Lozin, R. Mosca
Maximum independent set problem and P_5-free graphs
Manuscript 2004

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

[1117]

A. Brandstaedt, V.V. Lozin
A note on \alpha-redundant vertices in graphs.
Discrete Appl. Math. 108 (2001) 301-308

Polynomial [$O(V^8)$] on (P,P₇)-free

[1351]

V.E. Alekseev, V.V. Lozin
Augmenting graphs for independent sets
Discrete Appl. Math. 145, No.1 3-10 (2004)

Polynomial on (P,P₈)-free

[1306]

M.U. Gerber, A. Hertz, V.V. Lozin
Stable sets in two subclasses of banner-free graphs
Discrete Appl. Math. 132 121-136 (2004)

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 on (P₅,P₂ ∪ P₃)-free

[1350]

V.E. Alekseev
On easy and hard hereditary classes of graphs with respect to the independent set problem
Discrete Appl. Math. 132, No.1-3 17-26 (2003)

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 co-hereditary clique-Helly

[1298]

E. Prisner
Hereditary clique-helly graphs
J. Comb. Math. Comb. Comput 14 216-220 (1993)

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.

Polynomial

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

Monopolarity

[?]

Input: A graph G in this class.

Output: True iff G is monopolar.

Polynomial

Polynomial from XP on maximum independent set and Linear decomposition time
Polynomial from XP on minimum clique cover and Linear decomposition time

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

Polarity

[?]

Input: A graph G in this class.

Output: True iff G is polar.

Polynomial

Polynomial from Polarity 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 rankwidth and Linear decomposition time

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.

Linear

Polynomial from FPT on booleanwidth and Polynomial decomposition time
Polynomial from FPT on cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time
Polynomial from Weighted independent set on the complement

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

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 rankwidth and Linear decomposition time
Polynomial from FPT-Linear on cliquewidth and Polynomial decomposition time
Polynomial from XP on maximum independent set and Linear decomposition time
Polynomial from XP on maximum induced matching and Linear decomposition time
Polynomial from XP on minimum clique cover and Linear decomposition time

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

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

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
Polynomial from FPT on booleanwidth and Polynomial 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
Polynomial from XP on maximum independent set and Linear decomposition time
Polynomial from XP on minimum clique cover and Linear decomposition time

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 (P₅,gem)-free

[1170]

H. Bodlaender, A. Brandstaedt, D. Kratsch, M. Rao, J. Spinrad
Linear time algorithms for some NP-complete problems on (P_5, gem)-free graphs.
Manuscript 2003

Polynomial on 3K₁-free [trivial]
Polynomial on 4K₁-free [trivial]
Polynomial on 5K₁-free [trivial]
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 on (K_1,4,P,P₅,fork)-free

[1103]

A. Brandstaedt, P.L Hammer
On the stability number of claw-free, P_5-free and more general graphs.
Rutcor Research Report 27-97 1997

Polynomial [$O(n^5)$] on (K_1,4,P₅)-free

[1110]

R. Mosca
Polynomial algorithms for the maximum stable set problem on particular classes of P_5-free graphs
Information Processing Letters 61 (1997) 137-144

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,P₅)-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 (K_2,3,P₅)-free

[1110]

R. Mosca
Polynomial algorithms for the maximum stable set problem on particular classes of P_5-free graphs
Information Processing Letters 61 (1997) 137-144

Polynomial [$O(n^6)$] on (K_3,3,P₅)-free
Polynomial [$O(n^8)$] on (K_4,4,P₅)-free
Polynomial on (P,P₅)-free

[1353]

A. Brandstaedt, C.T. Hoang
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
Theoretical Comp. Sci. 389, No.1-2, 295-306 (2007)

Polynomial [$O(V^9 E)$] on (P,P₇)-free

[1452]

R. Mosca
Stable sets of maximum weight in (P_7, banner)-free graphs
Discrete Math. 308 Issue 1 20-33 (2008)

Polynomial on (P₅,X₈₂,X₈₃)-free

[1246]

V. Alekseev, P. Lozin, R. Mosca
Maximum independent set problem and P_5-free graphs
Manuscript 2004

Polynomial [$O(n^4)$] on (P₅,claw)-free

[1110]

R. Mosca
Polynomial algorithms for the maximum stable set problem on particular classes of P_5-free graphs
Information Processing Letters 61 (1997) 137-144

Polynomial on (P₅,co-fork)-free

[1161]

A. Brandstaedt, R. Mosca
On the structure and stability number of P_5 and co-chair-free graphs.
To appear in Discrete Appl. Math.

Polynomial on (P₅,cricket)-free

[1110]

R. Mosca
Polynomial algorithms for the maximum stable set problem on particular classes of P_5-free graphs
Information Processing Letters 61 (1997) 137-144

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 (P₅,house)-free

[1109]

V. Giakoumakis, I. Rusu
Weighted parameters in (P_5,\overline{P_5})-free graphs
Discrete Appl. Math. 80 (1997) 255-261

Polynomial on P₅-free

[1635]

D. Lokshantov, M. Vatshelle, Y. Villanger
Independent set in P5-free graphs in polynomial time
Accepted for publication

Polynomial on P₆-free

[1839]

A. Grzesik, T. Klimosova, M. Pilipczuk
Polynomial-time Algorithm for Maximum Weight Independent Set on P6-free Graphs
ACM Transactions on Algorithms 18 No.1 1-57 (2022)

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]

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 [$O(VE)$] on co-gem-free
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 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 [$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 semi-P₄-sparse

[402]

J.L. Fouquet, V. Giakoumakis
On semi--$P_4$--sparse graphs
Discrete Math. 165/166 1997 277--300

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)

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

Graphclass: (3K1,paw)-free

Complement classes

Forbidden subgraphs

Inclusions

Map

Minimal superclasses

Maximal subclasses

Speed

Parameters

Problems

Parameter decomposition

Unweighted problems

Weighted problems

Graphclass: (3K₁,paw)-free