In graph theory, a perfect graph is a graph in which the chromatic number of any generated subgraph is equal to the size of the maximum clique of this subgraph. Thanks to the , it has been known since 2002 that perfect graphs are the same as Berge graphs . A graph G is a Berge graph if neither G nor its complement has generated cycles of odd length (5 or more edges).
Perfect graphs include many important families of graphs and provide a unification of the results associated with the coloring and clicks of these families. For example, in all perfect graphs , the coloring problem, the maximum clique problem, and the maximum independent set problem can be solved in polynomial time . In addition, some important minimax combinatorics theorems, such as the Dilworth theorem , can be stated in terms of perfect graphs and some associated graphs.
The theory of perfect graphs has been developing since the work of 1958 by , which in modern language can be interpreted as the statement that the complement of a bipartite graph is a perfect graph. This result can be considered as a simple equivalent of the Koenig theorem , a much earlier result regarding matching and vertex coverings in bipartite graphs. The first use of the term “ perfect graph ” appeared in 1963 in an article by , where the name “Counts of Berge” came from. In this article, he combined the result of Galai with some similar results by determining perfect graphs and hypothesized the equivalence of perfect graphs and Berge graphs. The hypothesis was proved in 2002 as a .
Content
Families of Perfect Graphs
Some of the well-known perfect graphs:
- Bipartite graphs - a graph that can be colored in two colors. The family includes forests , graphs without cycles.
- Edge graphs of bipartite graphs (see Koenig theorem ). Rook graphs (edge graphs of complete bipartite graphs ) are a special case.
- Chordal graphs are graphs in which any cycle of length 4 or more vertices has a chord , that is, an edge between two vertices of a cycle that is not included in the cycle. This class includes forests, "k" -trees (maximal graphs with a given tree width ), split graphs (graphs that can be divided into a clique and an independent set), block graphs (graphs that have any biconnected component have a clique), interval columns (columns in which each vertex corresponds to the line segment, and each rib - a nonempty intersection segments), trivially perfect graphs (interval graphs for nested intervals) threshold counts (graphs in which two adjacent vertices when their total weight provost walking a certain threshold), a mill (formed by combining the same CPC and having a common point for all CPC) and (chordal graphs in which the length of each cycle of six or more has an odd chord).
- A comparability graph formed from partially ordered sets by connecting pairs of elements with an edge if they are connected in partial order. This family includes bipartite graphs, additions of interval graphs, trivially perfect graphs, threshold graphs, mills, permutation graphs (graphs in which edges correspond to pairs of elements in the reverse order) and cographs (graphs formed by recursive operations of combining disjoint graphs and addition).
- Perfectly ordered graphs are graphs that can be ordered in such a way that the greedy coloring algorithm is optimal for any generated prodgraph. This family includes bipartite graphs, chordal graphs, comparability graphs, distance-inherited graphs (in which the shortest distance in connected generated subgraphs is the shortest distance in the graph itself) and windmills having an odd number of vertices.
- Trapezoidal graphs are the intersection graphs of trapeziums whose bases lie on two parallel lines. This family includes interval graphs, trivially perfect graphs, pore graphs, mills, and permutation graphs. Many additions to these graphs are a subset of the graphs of comparability.
Connection with minimax theorems
In all graphs, the click number gives the minimum border of the chromatic number, since in the click all vertices must be painted in different colors. Perfect graphs are those for which the lower bound is accurate not only for the entire graph, but also for all its generated subgraphs. For graphs that are not perfect, the chromatic number and clique number may vary. So, for example, for a cycle of length 5, 3 paints are needed, and the maximum click has a size of 2.
The proof that the graph is perfect can be considered as a minimax theorem - the minimum number of colors required to color these graphs is equal to the size of the maximum clique. Many important minimax combinatorics theorems can be expressed in these terms. For example, the Dilworth theorem states that the minimum number of chains when dividing a partially ordered set by chains is equal to the maximum size of , and can be rephrased as saying that the complement of the graphs of comparability is perfect. states that the minimum number of anti-chains when divided into anti-chains is equal to the maximum size of chains and corresponds in the same way to the perfection of the graphs of comparability.
The perfection of the permutation graphs is equivalent to the statement that in any sequence of ordered elements the length of the largest decreasing subsequence is equal to the minimum number of sequences when divided into increasing subsequences. The Erdшаos – Szekeres theorem is easily derived from this statement.
Koenig's theorem in graph theory states that the minimum vertex coverage of a bipartite graph corresponds to the maximum matching and vice versa. It can be interpreted as the perfection of complements of bipartite graphs. Another theorem on bipartite graphs, that the chromatic index is equal to the maximum degree of a graph, is equivalent to the perfection of the edge graph of bipartite graphs.
Characteristics and theorems on perfect graphs
In his first work on perfect graphs, Berge put forward two important hypotheses about their structure, and they were proved later.
The first of these theorems was the Laszlo Lovas perfect graph theorem (1972), which states that a graph is perfect if and only if its complement is perfect. Thus, perfection (defined as the equality of the maximum clique size and the chromatic number in any generated subgraph) is equivalent to the maximum size of the independent set and the number of click coverage.
The second theorem, expressed by Berge as a hypothesis, provided a characterization of forbidden graphs for a perfect graph.
A generated cycle of odd length at least 5 is called a hole of odd length . A subgraph generated by an extra odd hole is called an odd anti-hole . An odd cycle of length greater than 3 cannot be perfect, because its chromatic number is three, and the click number is two. Similarly, an additional odd cycle graph of length 2 k + 1 cannot be perfect because its chromatic number is k + 1 and its clique number is k . (Or the imperfection of this graph follows from the theorem on perfect graphs and the imperfection of complements to odd cycles). Since these graphs are not perfect, each perfect graph must be a Berge graph, a graph without odd holes and without odd anti-holes. Berge expressed the converse hypothesis that any graph of Berge is perfect. This is finally proved by the , , Semur , and Thomas (2006).
The perfect graph theorem has a short proof, but the proof of the strong perfect graph theorem is long and technically complicated. It is based on the structural decomposition of Berge graphs. Close decomposition methods were also born as a result of studying other classes of graphs, in particular, graphs without claws .
Perfect Graph Algorithms
For all perfect graphs, the graph coloring problem, the maximal clique problem, and the maximal independent set problem can be solved in polynomial time (Grötschel, Lovász, Schrijver, 1988) [1] . The general case algorithm uses the ellipsoid method for linear programming , but combinatorial algorithms known for many special cases are more efficient.
For many years, the question of the computational complexity of recognizing Berge graphs and perfect graphs remained open. It immediately follows from the definition of Berge graphs that their recognition is a problem from the class co-NP [2] . Finally, after proving the strong theorem on perfect graphs, a polynomial algorithm was found.
Notes
- ↑ Martin Grötschel, László Lovász, Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. - Springer-Verlag, 1988 .-- S. 273-303. . See chapter 9, “Stable Sets in Graphs”
- ↑ Lovász, László. Selected Topics in Graph Theory, Vol. 2 / Beineke, Lowell W .; Wilson, Robin J. (Eds.). - Academic Press, 1983. - S. 55-87 .
Literature
- Berge, Claude. Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. - 1961.- T. 10 . - S. 114 .
- Berge, Claude. Perfect graphs. - Calcutta: Indian Statistical Institute, 1963. - S. 1-21 .
- , , Seymour, Paul; , and Thomas, Robin; Vušković, Kristina. Recognizing Berge graphs // Combinatorica. - 2005. - T. 25 , no. 2 . - S. 143-186 . - DOI : 10.1007 / s00493-005-0012-8 .
- , , Seymour, Paul; , and Thomas, Robin; . The strong perfect graph theorem // Annals of Mathematics . - 2006. - T. 164 , no. 1 . - S. 51—229 . - DOI : 10.4007 / annals.2006.164.51 .
- Gallai, Tibor. Maximum-minimum Sätze über Graphen // Acta Math. Acad. Sci. Hungar. - 1958. - T. 9 , no. 3-4 . - S. 395-434 . - DOI : 10.1007 / BF02020271 .
- Golumbic, Martin Charles. Algorithmic Graph Theory and Perfect Graphs . - Academic Press, 1980. Archived May 22, 2010.
- Lovász, László. Normal hypergraphs and the perfect graph conjecture // Discrete Mathematics . - 1972. - T. 2 , no. 3 . - S. 253-267 . - DOI : 10.1016 / 0012-365X (72) 90006-4 .
- Lovász, László. A characterization of perfect graphs // Journal of Combinatorial Theory, Series B. - 1972.- T. 13 , no. 2 . - S. 95-98 . - DOI : 10.1016 / 0095-8956 (72) 90045-7 .
Links
- The Strong Perfect Graph Theorem by .
- Open problems on perfect graphs , maintained by the American Institute of Mathematics .
- Perfect Problems , maintained by Václav Chvátal.
- Information System on Graph Class Inclusions : perfect graph