Graphclass: bipartite ∩ distance-hereditary

References

[34]

G. Ausiello, A. D'Atri, M. Moscarini
Chordality properties on graphs and minimal conceptual connections in semantic data models
J. Comput. Syst. Sciences 33 1986 179--202

[290]

A. D'Atri, M. Moscarini
Distance-hereditary graphs, Steiner trees, and connected domination.
SIAM J. Comput. 17, No.3, 521-538 (1988). [ISSN 0097-5397]

Equivalent classes

Only references for direct inclusions are given. Where no reference is given for an equivalent class, check other equivalent classes or use the Java application.

(6,2)-chordal ∩ bipartite
[1382]
A. Brandstaedt, V.B. Le, J. Spinrad
Graph classes: a survey
SIAM Monographs on discrete mathematics and applications (1999)

[290]
A. D'Atri, M. Moscarini
Distance-hereditary graphs, Steiner trees, and connected domination.
SIAM J. Comput. 17, No.3, 521-538 (1988). [ISSN 0097-5397]
bipartite ∩ module-composed
(domino,hole,odd-cycle)-free [from the set of forbidden subgraphs]
domino-free ∩ modular
[57]
H.--J. Bandelt, H.M. Mulder
Distance--hereditary graphs
J. Comb. Theory (B) 41 1986 182--208
independent module-composed
[1362]
F. Gurski, E. Wanke
On module-composed graphs
35th Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. WG'09,Lecture Notes in Comp. Sci. 5911 166--177 (2009)

Complement classes

(anti-hole,co-domino,odd anti-cycle)-free

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 bipartite $\cap$ distance--hereditary

Minimal superclasses

(6,1)-chordal ∩ bipartite (known proper)
(C_n+6,odd-cycle)-free (known proper)
Helly circle (known proper)
X-conformal ∩ bipartite ∩ hereditary X-chordal (known proper)
bipartite ∩ co-perfectly orderable (known proper)
bipartite ∩ weakly chordal (known proper)
chordal bipartite (known proper)
circle ∩ diamond-free (known proper)
comparability ∩ distance-hereditary (known proper)
(domino,gem,hole,house,net)-free (known proper)
hereditary perfect elimination bipartite (known proper)
(hole,odd-cycle)-free (known proper)
module-composed (known proper)
pairwise compatibility
[1774]
T. Calamoneri, B. Sinaimeri
Pairwise compatibility graphs: A survey
Accepted for SIAM Review

(known proper)
probe bipartite distance-hereditary [trivial] (known proper)

Maximal subclasses

(0,2)-colorable ∩ chordal (known proper)
(2K₂,C₅,triangle)-free (known proper)
2K₂-free ∩ bipartite (known proper)
K₃-minor-free (known proper)
(P₄,triangle)-free (known proper)
bipartite ∩ bridged (known proper)
bipartite chain (known proper)
cycle-free (known proper)
difference (known proper)
tree (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 (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.

Unbounded

Unbounded from degeneracy

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 cutwidth
Unbounded from degeneracy
Unbounded from maximum degree
Unbounded from pathwidth
Unbounded from treewidth

Unbounded on binary tree ∩ partial grid

[1757]

(no preview available)

Unbounded on complete bipartite [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 degeneracy

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 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 degeneracy
Unbounded from treewidth

carvingwidth

[?]

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

Unbounded

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from degeneracy
Unbounded from maximum degree
Unbounded from treewidth

chromatic number

[?]

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

Bounded

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 rankwidth

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 probe bipartite distance-hereditary
Bounded on probe distance-hereditary

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 chromatic number

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

Unbounded

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from carvingwidth
Unbounded from degeneracy
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 on complete bipartite [by definition]

diameter

[?]

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

Unbounded

Unbounded on binary tree ∩ partial grid [trivial]
Unbounded on caterpillar [by definition]
Unbounded on linear forest [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 complete bipartite [trivial]

distance to clique

[?]

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

Unbounded

Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to cograph
Unbounded from maximum independent set
Unbounded from maximum induced matching
Unbounded from minimum clique cover
Unbounded from minimum dominating set

distance to cluster

[?]

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

Unbounded

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

Unbounded on complete bipartite [by definition]

distance to co-cluster

[?]

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

Unbounded

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

distance to cograph

[?]

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

Unbounded

Unbounded from diameter

Unbounded on 2K₂-free ∩ bipartite

distance to linear forest

[?]

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

Unbounded

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from degeneracy
Unbounded from distance to block
Unbounded from distance to outerplanar
Unbounded from pathwidth
Unbounded from treewidth

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

distance to outerplanar

[?]

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

Unbounded

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from degeneracy
Unbounded from treewidth

genus

[?]

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

Unbounded

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from degeneracy

Unbounded on complete bipartite [by definition]

max-leaf number

[?]

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

Unbounded

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

Bounded

Bounded from chromatic number

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

Unbounded

Unbounded from acyclic chromatic number
Unbounded from degeneracy

Unbounded on (C₄,P₃,triangle)-free [by definition]
Unbounded on caterpillar [by definition]
Unbounded on complete bipartite [by definition]
Unbounded on disjoint union of stars [by definition]

maximum independent set

[?]

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

Unbounded

Unbounded from diameter
Unbounded from maximum induced matching
Unbounded from minimum dominating set

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

maximum induced matching

[?]

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

Unbounded

Unbounded from diameter

Unbounded on (P₄,triangle)-free [by definition]
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 acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from degeneracy
Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to cograph
Unbounded from distance to linear forest
Unbounded from distance to outerplanar
Unbounded from maximum induced matching
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.

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

Unbounded

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from degeneracy
Unbounded from treewidth

rankwidth

[?]

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

Bounded

Bounded from booleanwidth
Bounded from cliquewidth

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

Unbounded from acyclic chromatic number
Unbounded from book thickness
Unbounded from branchwidth
Unbounded from degeneracy

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 degeneracy
Unbounded from diameter
Unbounded from distance to block
Unbounded from distance to cluster
Unbounded from distance to co-cluster
Unbounded from distance to cograph
Unbounded from distance to linear forest
Unbounded from distance to outerplanar
Unbounded from maximum induced matching
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

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)

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.

Linear

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

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 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 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
Polynomial from Colourability
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 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 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 from XP on chromatic number and Linear decomposition time
Polynomial from XP on maximum clique and Linear decomposition time

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

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.

Polynomial

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

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)

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 cliquewidth and Linear decomposition time
Polynomial from FPT on cliquewidth and Polynomial decomposition time
Polynomial from FPT on rankwidth and Linear decomposition time

Linear on (0,3)-colorable
Linear on bipartite [trivial]
Linear on paw-free ∩ perfect
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 on circular perfect

[1408]

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

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)

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 on chordal bipartite

[1583]

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

Graph isomorphism

[?]

Input: Graphs G and H in this class

Output: True iff G and H are isomorphic.

Polynomial

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

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

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

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

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]

Monopolarity

[?]

Input: A graph G in this class.

Output: True iff G is monopolar.

Linear

Linear on monopolar [trivial]
Polynomial on bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
Polynomial on bipartite ∪ co-bipartite ∪ split
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)

Polarity

[?]

Input: A graph G in this class.

Output: True iff G is polar.

Linear

Recognition

[?]

Input: A graph G.

Output: True iff G is in this graph class.

Linear

From the constituent classes.

Polynomial on bipartite ∩ module-composed
Polynomial on domino-free ∩ modular

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

Polynomial on 4-colorable [trivial]
Polynomial on 5-colorable [trivial]
Polynomial on 6-colorable [trivial]
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 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 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

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

[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

[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 bipartite
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(V^2 \log \log V)$] on circular trapezoid
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 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 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^4)$] on weakly chordal

[997]

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

Graphclass: bipartite ∩ distance-hereditary

References

Equivalent classes

Complement classes

Related classes

Inclusions

Map

Minimal superclasses

Maximal subclasses

Speed

Parameters

Problems

Parameter decomposition

Unweighted problems

Weighted problems