Graphclass: perfect

Definition:

A graph is perfect if for all induced subgraphs H: \chi(H) = \omega(H), where \chi is the chromatic number and \omega is the size of a maximum clique.

References

[88]
C. Berge
Les probl\`emes de colorations en th\'eorie des graphes
{\sl Publ. Inst. Stat. Univ. Paris, 9} 1960 123--160
[89]
C. Berge
F\"arbung von Graphen deren saemtliche bzw. deren ungeraden Kreise starr sind
Wiss. Zeitschr. Martin-Luther-Univ. Halle-Wittenberg 114 1961
[95]
C. Berge
Motivations and history of some of my conjectures
Discrete Math. 165/166 61--70 1997
[96]
C. Berge, V. Chv\'atal (eds.)
Topics on perfect graphs
Annals of Discrete Math. 21 1984
[453]
M.C. Golumbic
Algorithmic Graph Theory and Perfect Graphs
Academic Press, New York 1980
[737]
L. Lov\'asz
Perfect graphs
{\sl Selected Topics in Graph Theory} 2, {\sc L.W. Beineke, R.J. Wilson}eds.,Academic Press, New York 1983 55--87
[1026]
B. Toft
Coloring, stable sets and perfect graphs
In: {\sc R. Graham, M. Gr\"otschel, L. Lov\'asz}, eds.,Handbook of Combinatorics, Vol. I, North-Holland, 1995 0 233--288

;

[476]
M. Gr\"otschel, L. Lov\'asz, A. Schrijver
The ellipsoid method and its consequences in combinatorial optimization
Combinatorica 1 169--197, 1981 Corrigendum
[1226]
M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic
Cleaning for Bergeness
manuscript 2003
[1227]
M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic
Recognizing Berge graphs
manuscript 2003
[1228]
M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic
A polynomial algorithm for recognizing Berge graphs
manuscript 2003
[1588]
The decycling number of graphs
S. Bau, L.W. Beineke
Australas. J. Comb. 25 285-298 (2002)
[1589]
R.M. Karp
Reducibility among combinatorial problems
Complexity of Computer Computations (R.E. Miller, J.W. Thatcher, ed.), Plenum Press, New York-London 85-103 (1972)

Equivalent classes

[+]Details

Complement classes

self-complementary

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

[+]Details

Minimal superclasses

[+]Details

Maximal subclasses

[+]Details

Parameters

Parameters are in beta. If you find any irregularities, please contact us!

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 [+]Details
booleanwidth
[?]
Consider the following decomposition of a graph $G$ which is defined as a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. The function $\text{cut-bool} \colon 2^{V(G)} \rightarrow R$ is defined as $\text{cut-bool}(A)$ := $\log_2|\{S \subseteq V(G) \backslash A \mid \exists X \subseteq A \colon S = (V(G) \backslash A) \cap \bigcup_{x \in X} N(x)\}|$. Every edge $e$ in $T$ partitions the vertices $V(G)$ into $\{A_e,\overline{A_e}\}$ according to the leaves of the two connected components of $T - e$. The booleanwidth of the above decomposition $(T,L)$ is $\max_{e \in E(T)\;} \{ \text{cut-bool}(A_e)\}$. The booleanwidth of a graph $G$ is the minimum booleanwidth of a decomposition of $G$ as above.
Unbounded [+]Details
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 vertices 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 [+]Details
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 [+]Details
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.
Unknown to ISGCI [+]Details
cliquewidth
[?]
The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:
  • creation of a vertex with label $i$,
  • disjoint union,
  • renaming labels $i$ to label $j$, and
  • connecting all vertices with label $i$ to all vertices with label $j$.
Unbounded [+]Details
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 [+]Details
degeneracy
[?]
The degeneracy of a graph $G$ is the smallest integer $k$ such that each subgraph of $G$ contains a vertex of degree at most $k$.
Unknown to ISGCI [+]Details
diameter
[?]
The diameter of a graph $G$ is the length of the longest shortest path between any two vertices in $G$.
Unknown to ISGCI [+]Details
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 [+]Details
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.
Unknown to ISGCI [+]Details
distance to cluster
[?]
A cluster cluster graph 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.
Unknown to ISGCI [+]Details
distance to co-cluster
[?]
Let $G$ be a graph. Its distance to co-cluster is the minimum number of vertices that have to be deleted to obtain a complement of a cluster graph.
Unknown to ISGCI [+]Details
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 [+]Details
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 [+]Details
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 [+]Details
genus
[?]
The genus $g$ of a graph $G$ is the minimum number of handles over all surfaces on which $G$ can be embedded.
Unknown to ISGCI [+]Details
maximum clique
[?]
The parameter maximum clique of a graph $G$ is the largest number of vertices in a complete subgraph of $G$.
Unknown to ISGCI [+]Details
maximum degree
[?]
The maximum degree of a graph $G$ is the largest number of neighbors of a vertex in $G$.
Unbounded [+]Details
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$.
Unknown to ISGCI [+]Details
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 a induced matching in $G$.
Unknown to ISGCI [+]Details
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 [+]Details
max-leaf number
[?]
The max-leaf number of a graph $G$ is the maximum number of leaves in a spanning tree of $G$.
Unbounded [+]Details
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.
Unknown to ISGCI [+]Details
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$.
Unknown to ISGCI [+]Details
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 [+]Details
rankwidth
[?]
Let $M$ be the $|V| \times |V|$ adjacency matrix of a graph $G$. The cut rank of a set $A \subseteq V(G)$ is the rank of the submatrix of $M$ induced by the rows of $A$ and the columns of $V(G) \backslash A$. A rank decomposition of a graph $G$ is a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. Any edge $e$ in the tree $T$ splits $V(G)$ into two parts $A_e, B_e$ corresponding to the leaves of the two connected components of $T - e$. The width of an edge $e \in E(T)$ is the cutrank of $A_e$. The width of the rank-decomposition $(T,L)$ is the maximum width of an edge in $T$. The rankwidth of the graph $G$ is the minimum width of a rank-decomposition of $G$.
Unbounded [+]Details
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 [+]Details
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 [+]Details
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 [+]Details

Problems

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

Parameter decomposition

booleanwidth decomposition
[?]
Input: A graph G in this class.
Output: An expression that constructs G according to the rules for booleanwidth, using only a constant number of labels.
Undefined if this class has unbounded booleanwidth.
Unknown to ISGCI [+]Details
cliquewidth decomposition
[?]
Input: A graph G in this class.
Output: An expression that constructs G according to the rules for cliquewidth, using only a constant number of labels.
Undefined if this class has unbounded cliquewidth.
Unknown to ISGCI [+]Details
cutwidth decomposition
[?]
Input: A graph G in this class and an integer k.
Output: True iff the cutwidth of G is at most k.
NP-complete [+]Details
treewidth decomposition
[?]
Input: A graph G in this class and an integer k.
Output: True iff the treewidth of G is at most k.
NP-complete [+]Details

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.
Polynomial [+]Details
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.
Polynomial [+]Details
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 Si, such that whenever two vertices are in the same set Si, they are adjacent.
Polynomial [+]Details
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 [+]Details
Domination
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
NP-complete [+]Details
Feedback vertex set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.
NP-complete [+]Details
Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
GI-complete [+]Details
Hamiltonian cycle
[?]
Input: A graph G in this class.
Output: True iff G has a simple cycle that goes through every vertex of the graph.
NP-complete [+]Details
Hamiltonian path
[?]
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.
NP-complete [+]Details
Independent dominating set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
NP-complete [+]Details
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.
Polynomial [+]Details
Maximum cut
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
NP-complete [+]Details
Recognition
[?]
Input: A graph G.
Output: True iff G is in this graph class.
Polynomial [+]Details

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.
Polynomial [+]Details
Weighted feedback vertex set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.
NP-complete [+]Details
Weighted independent dominating set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.
NP-complete [+]Details
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.
Polynomial [+]Details
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 [+]Details