Perfect graph

perfect graph

Examples:
Triangulated graphs Bipartite graph Complete graph Co-graphs Comparability graph

In graph theory , a graph is called perfect if it holds for every induced subgraph that its clique number agrees with its chromatic number . An induced subgraph of a graph consists of a subset of the nodes and all incident edges .

properties

In a perfect graph, chromatic number, clique number and stability number can be calculated in polynomial running time, the calculation of which is NP-complete on general graphs . It can be determined in polynomial time whether a graph is perfect. Examples of perfect graphs are bipartite graphs , edge graphs , bipartite graphs and their complements. They form the basis for the strong perfect graph set and are therefore also referred to as simple perfect graphs in this context . Other examples of perfect graphs are triangulated graphs and chordal bipartite graphs .

According to the theorem about perfect graphs , the following statements are equivalent:

${\ displaystyle G}$ is a perfect graph .
The complement graph of is perfect. ${\ displaystyle G}$
${\ displaystyle G}$ contains neither an odd cycle of length at least 5 nor the complement graph of such a cycle as an induced subgraph . Graphs with this property are called Berge graphs .

The second characteristic is known as the weak perfect graph theorem , was proven by László Lovász in 1972 and is therefore now called Lovász's theorem . The third characteristic is also known as the strong perfect graph theorem and was only proven in May 2002. Both statements were made as a presumption by Claude Berge as early as 1960 .

Theorems about perfect graphs

In all graphs , the clique number represents a lower limit for the chromatic number, since all nodes in a clique must be assigned different colors in each correct color. The perfect graphs are those for which this lower bound is fixed, not only in the graph itself, but in all induced subgraphs . For graphs that are not perfect, the chromatic number and the clique number may differ. For example, a cycle of length five requires three colors in each coloration , but its largest clique is size two.

Proof that a class of graphs is perfect can be seen as the min-max theorem : the minimum number of colors required for these graphs corresponds to the maximum size of a clique . Many important min-max theorems in combinatorics can be expressed with these terms.

For example, Dilworth's theorem states that the minimum number of chains in a partition of a partial order in chains corresponds to the maximum size of an antichain and can be reformulated so that the complement graphs of comparability graphs are perfect. Mirsky's theorem states that the minimum number of anti-chains in a partition in anti-chains corresponds to the maximum size of a chain and in the same way corresponds to the perfection of comparability graphs.

The perfection of permutation graphs corresponds to the statement that in every sequence of ordered elements the length of the longest ascending sub- sequence corresponds to the minimum number of sequences in a partition into ascending sub-sequences. Erdős-Szekeres' theorem is a simple consequence of this statement.

The set of king states that a minimum vertex cover in a bipartite graph a maximum matching corresponds and vice versa. It can be interpreted as the perfection of the complement graphs of bipartite graphs. Another theorem about bipartite graphs, that their chromatic index corresponds to their maximum nodal degree , corresponds to the perfection of the edge graphs of bipartite graphs.

A cycle with seven nodes and its complement graph , each showing optimal coloring and maximal clique . Because no graph uses a number of colors equal to its clique size, none is perfect.

The weak perfect graph theorem by László Lovász says that a graph is perfect if and only if its complement graph is perfect. The perfection of a graph, defined as the equality of the maximum clique size and the chromatic number in each induced subgraph, corresponds to the statement that the size of a maximum independent set is equal to the clique coverage number.

The strong perfect graph theorem by Chudnovsky, Robertson, Seymour, and Thomas provides a different characterization of perfect graphs. An induced cycle with an odd length of at least 5 is called an odd hole . An induced subgraph that represents the complement graph of an odd hole is called an odd anti- hole . An odd cycle longer than 3 cannot be perfect because its chromatic number is three and its clique number is two. Similarly, the complement graph of an odd cycle of length cannot be perfect since its chromatic number and its clique number are. Alternatively, this follows from the perfect graph theorem and from the fact that the complementary odd cycle is not perfect. Because these graphs are imperfect, every perfect graph must be a mountain graph, a graph with no odd holes and no odd anti-holes. ${\ displaystyle 2 \ cdot k + 1}$ ${\ displaystyle k + 1}$ ${\ displaystyle k}$

literature

Vašek Chvátal : Perfect Problems . about perfect graphs.
Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke: Exact algorithms for difficult graph problems . Springer-Verlag, Berlin / Heidelberg 2010, ISBN 978-3-642-04499-1

Web links

perfect - Entry in the Information System on Graph Classes and their Inclusions
Berge - Entry in the Information System on Graph Classes and their Inclusions

Individual evidence

↑ Grötschel , Lovász , Alexander Schrijver : Geometric Algorithms and Combinatorial Optimization . Springer-Verlag, 1988, Chapter 9, Stable Sets in Graphs , pp. 273-303
↑ Chudnovsky , Cornuéjols, Liu, Seymour , Vušković: Recognizing Berge Graphs . In: Combinatorica , Vol. 25, No. 2, 2005, pp. 143-186
↑ Chudnovsky , Robertson , Seymour , Thomas : The strong perfect graph theorem . In: Annals of Mathematics , Vol. 164, 2006, pp. 51-229
↑ Lovász, László : A characterization of perfect graphs . In: Journal of Combinatorial Theory . 13, No. 2, 1972, pp. 95-98. doi : 10.1016 / 0095-8956 (72) 90045-7 .
^ Lovász, László : Perfect graphs . In: Academic Press . 1983, pp. 55-87.
^ Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: The strong perfect graph theorem . In: Annals of Mathematics . 164, No. 1, 2006, pp. 51-229. arxiv : math / 0212070 . doi : 10.4007 / annals.2006.164.51 .

[1] Grötschel , Lovász , Alexander Schrijver : Geometric Algorithms and Combinatorial Optimization . Springer-Verlag, 1988, Chapter 9, Stable Sets in Graphs , pp. 273-303

[2] Chudnovsky , Cornuéjols, Liu, Seymour , Vušković: Recognizing Berge Graphs . In: Combinatorica , Vol. 25, No. 2, 2005, pp. 143-186

[3] Chudnovsky , Robertson , Seymour , Thomas : The strong perfect graph theorem . In: Annals of Mathematics , Vol. 164, 2006, pp. 51-229

[4] Lovász, László : A characterization of perfect graphs . In: Journal of Combinatorial Theory . 13, No. 2, 1972, pp. 95-98. doi : 10.1016 / 0095-8956 (72) 90045-7 .

[5] Lovász, László : Perfect graphs . In: Academic Press . 1983, pp. 55-87.

[6] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: The strong perfect graph theorem . In: Annals of Mathematics . 164, No. 1, 2006, pp. 51-229. arxiv : math / 0212070 . doi : 10.4007 / annals.2006.164.51 .