Jump to content

Perfect graph: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
source comparability graph lead paragraph
Line 44: Line 44:
===Comparability graphs===
===Comparability graphs===
[[File:Poset et graphe de comparabilité.svg|thumb|upright=1.2|The [[Hasse diagram]] of a partially ordered set, and its [[comparability graph]]]]
[[File:Poset et graphe de comparabilité.svg|thumb|upright=1.2|The [[Hasse diagram]] of a partially ordered set, and its [[comparability graph]]]]
A [[partially ordered set]] is defined by its set of elements, and a comparison relation <math>\le</math> on these elements, obeying the requirements that ≤ is a [[reflexive relation]] (for all elements <math>x</math>, <math>x\le x</math>), an [[antisymmetric relation]] (if <math>x\le y</math> and <math>y\le x</math>, then <math>x=y</math>, and a [[transitive relation]] (if <math>x\le y</math> and <math>y\le z</math>, then <math>x\le z</math>). Two distinct elements <math>x</math> and <math>y</math> are said to be ''comparable'' if <math>x\le y</math> or <math>y\le x</math>, and ''incomparable'' otherwise. For instance, the set inclusion operation <math>\subseteq</math> is the comparison relation of a partial order on any [[family of sets]]. The [[comparability graph]] of a partially ordered set is a graph with the set elements as its vertices, and with an edge connecting two vertices whenever those two elements are comparable. Its complement is called an ''incomparability graph''. The comparability graph is not enough to uniquely identify a partial order; different partial orders may have the same comparability graph. For instance, reversing all comparison relations between pairs of elements changes their order but does not change their comparability graph.
A [[partially ordered set]] is defined by its set of elements, and a comparison relation <math>\le</math> on these elements, obeying the requirements that ≤ is a [[reflexive relation]] (for all elements <math>x</math>, <math>x\le x</math>), an [[antisymmetric relation]] (if <math>x\le y</math> and <math>y\le x</math>, then <math>x=y</math>, and a [[transitive relation]] (if <math>x\le y</math> and <math>y\le z</math>, then <math>x\le z</math>). Two distinct elements <math>x</math> and <math>y</math> are said to be ''comparable'' if <math>x\le y</math> or <math>y\le x</math>, and ''incomparable'' otherwise. For instance, the set inclusion operation <math>\subseteq</math> is the comparison relation of a partial order on any [[family of sets]]. The [[comparability graph]] of a partially ordered set is a graph with the set elements as its vertices, and with an edge connecting two vertices whenever those two elements are comparable. Its complement is called an ''incomparability graph''. The comparability graph is not enough to uniquely identify a partial order; different partial orders may have the same comparability graph. For instance, reversing all comparison relations between pairs of elements changes their order but does not change their comparability graph.{{r|harzheim-2005}}


Finite comparability graphs (and their complementary incomparability graphs) are always perfect. A clique, in a comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a [[Chain (order theory)|chain]], and it is [[total order|linearly ordered]] by the given partial order. An independent set comes from a subset of elements no two of which are comparable; such a subset is called an [[antichain]]. Thus, a coloring of a comparability graph is a partition of its elements into antichains, and a clique cover is a partition of its elements into chains. [[Dilworth's theorem]], in the theory of partial orders, states that for every finite partial order, the size of the largest antichain equals the minimum number of chains into which the elements can be partitioned. In the language of graphs, this can be stated as: every finite comparability graph is perfect. Similarly, [[Mirsky's theorem]] states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph is perfect. These two theorems are equivalent via the perfect graph theorem, but Mirsky's theorem is easier than Dilworth's theorem to prove directly: if each element is labeled by the size of the largest chain in which it is maximal, then the subsets with equal labels form a partition into antichains, with the number of antichains equal to the size of the largest chain overall.{{r|mirsky-1971}}
Finite comparability graphs (and their complementary incomparability graphs) are always perfect.{{r|berge-1967}} A clique, in a comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a [[Chain (order theory)|chain]], and it is [[total order|linearly ordered]] by the given partial order. An independent set comes from a subset of elements no two of which are comparable; such a subset is called an [[antichain]]. Thus, a coloring of a comparability graph is a partition of its elements into antichains, and a clique cover is a partition of its elements into chains. [[Dilworth's theorem]], in the theory of partial orders, states that for every finite partial order, the size of the largest antichain equals the minimum number of chains into which the elements can be partitioned. In the language of graphs, this can be stated as: every finite comparability graph is perfect. Similarly, [[Mirsky's theorem]] states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph is perfect. These two theorems are equivalent via the perfect graph theorem, but Mirsky's theorem is easier than Dilworth's theorem to prove directly: if each element is labeled by the size of the largest chain in which it is maximal, then the subsets with equal labels form a partition into antichains, with the number of antichains equal to the size of the largest chain overall.{{r|mirsky-1971}}


Every bipartite graph is the comparability graph of a partial order. If a bipartite graph has its vertices colored, say red and blue, then it is the comparability graph for a comparison relation in which every red vertex is <math>\le</math> every blue vertex, every vertex is <math>\le</math> itself, and there are no other comparable pairs. In the partial orders constructed in this way, the largest chains consist of one red and one blue vertex. Thus, by connecting them through the theory of perfect graphs, Kőnig's theorem can be seen as a special case of Dilworth's theorem.{{r|perfect-1980}}
Every bipartite graph is the comparability graph of a partial order. If a bipartite graph has its vertices colored, say red and blue, then it is the comparability graph for a comparison relation in which every red vertex is <math>\le</math> every blue vertex, every vertex is <math>\le</math> itself, and there are no other comparable pairs. In the partial orders constructed in this way, the largest chains consist of one red and one blue vertex. Thus, by connecting them through the theory of perfect graphs, Kőnig's theorem can be seen as a special case of Dilworth's theorem.{{r|perfect-1980}}
Line 93: Line 93:
| title = Six Papers on Graph Theory
| title = Six Papers on Graph Theory
| year = 1963}}</ref>
| year = 1963}}</ref>

<ref name=berge-1967>{{cite book
| last = Berge | first = Claude | author-link = Claude Berge
| contribution = Some classes of perfect graphs
| mr = 0232694
| pages = 155–165
| publisher = Academic Press | location = London
| title = Graph Theory and Theoretical Physics
| year = 1967
| zbl = 0203.26403}}</ref>


<ref name=bg-2006>{{cite journal
<ref name=bg-2006>{{cite journal
Line 194: Line 204:
| volume = 89
| volume = 89
| year = 2004}}</ref>
| year = 2004}}</ref>

<ref name=harzheim-2005>{{cite book
| last = Harzheim | first = Egbert
| contribution = Comparability graphs
| doi = 10.1007/0-387-24222-8_12
| isbn = 0-387-24219-8
| mr = 2127991
| pages = 353–368
| publisher = Springer | location = New York
| series = Advances in Mathematics
| title = Ordered Sets
| volume = 7
| year = 2005
| zbl = 1072.06001}}</ref>


<ref name=hougardy-2006>{{cite journal
<ref name=hougardy-2006>{{cite journal

Revision as of 08:12, 29 January 2023

The graph of the 3-3 duoprism (the line graph of ) is perfect. Here it is colored with three colors, with one of its 3-vertex maximum cliques highlighted.

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time, despite their greater complexity for non-perfect graphs. In addition, several important minimax theorems in combinatorics, including Dilworth's theorem and Mirsky's theorem on partially ordered sets, Kőnig's theorem on matchings, and the Erdős–Szekeres theorem on monotonic sequences, can be expressed in terms of the perfection of certain associated graphs.

The perfect graph theorem states that the complement graph of a perfect graph is also perfect. The strong perfect graph theorem characterizes the perfect graphs in terms of certain forbidden induced subgraphs, leading to a polynomial time algorithm for testing whether a graph is perfect.

Definitions and characterizations

A clique in an undirected graph is a subset of its vertices that are all adjacent to each other. A graph coloring assigns a color to each vertex so that each two adjacent vertices have different colors. In particular, the vertices of any clique must all be assigned different colors, so the chromatic number (the minimum number of colors in any coloring) is always greater than or equal to the clique number, the number of vertices in the maximum clique. The perfect graphs are defined as the graphs for which these two numbers are equal, not just in the graph itself, but in every induced subgraph obtained by deleting some of its vertices.

Two complementary perfect graphs

The perfect graph theorem asserts that the complement graph of a perfect graph is itself perfect. The complement graph has the same vertices as the given graph, but a complementary adjacency relation: two vertices are adjacent, in the complement graph, if and only if they are not adjacent in the given graph. A clique, in the complement graph, corresponds to an independent set in the given. A coloring of the complement graph corresponds to a clique cover, a partition of the vertices of the given graph into cliques. The fact that the complement of a perfect graph is also perfect implies that, in itself, the independence number (the size of its maximum independent set), equals its clique cover number (the fewest number of cliques needed in a clique cover). More strongly, the same thing is true in every induced subgraph of the complement graph. This provides an alternative and equivalent definition of the perfect graphs: they are the graphs for which, in each induced subgraph, the independence number equals the clique cover number.[1]

A seven-vertex cycle and its complement, showing in each case an optimal coloring and a maximum clique (shown with heavy edges). Since neither graph uses a number of colors equal to its clique size, neither is perfect.

The strong perfect graph theorem gives a different way of defining perfect graphs, by their structure instead of by their properties. It is based on the existence of cycle graphs and their complements among the induced subgraphs of a given graph. A cycle of odd length, greater than three, is not a perfect graph: its clique number is two, but its chromatic number is three. By the perfect graph theorem, the complement of an odd cycle of length greater than three is also not perfect. The complement of a length-5 cycle is another length-5 cycle, but for larger odd lengths the complement is not a cycle. The strong perfect graph theorem asserts that these are the only forbidden induced subgraphs for the perfect graphs: a graph is perfect if and only if its induced subgraphs include neither an odd cycle of length greater than five, nor an odd anticycle of length greater than five. In this context, induced cycles that are not triangles are called "holes", and their complements are called "antiholes", so the strong perfect graph theorem can be stated more succinctly: a graph is perfect if and only if it has neither an odd hole nor an odd antihole.[2]

These results can be combined in another characterization of perfect graphs: they are the graphs for which the product of the clique number and independence number is greater than or equal to the number of vertices, and for which the same is true for all induced subgraphs. Because the statement of this characterization remains invariant under complementation of graphs, it implies the perfect graph theorem. One direction of this characterization follows easily from the original definition of perfect: the number of vertices in any graph equals the sum of the sizes of the color classes in an optimal coloring, and is less than or equal to the number of colors multiplied by the independence number. In a perfect graph, the number of colors equals the clique number, and can be replaced by the clique number in this inequality.[3] The other direction follows from the strong perfect graph theorem and the observation that in odd cycles of length greater than three the product of the clique number and independence number is one less than the number of vertices.

History

The theory of perfect graphs developed from a 1958 result of Tibor Gallai that in modern language can be interpreted as stating that the complement of a bipartite graph is perfect;[4] this result can also be viewed as a simple equivalent of Kőnig's theorem, a much earlier result relating matchings and vertex covers in bipartite graphs. The first use of the phrase "perfect graph" appears to be in a 1963 paper of Claude Berge. In this paper he unified Gallai's result with several similar results by defining perfect graphs, and he conjectured both the perfect graph theorem and the strong perfect graph theorem.[5] Until the strong perfect graph theorem was proven, the graphs described by it (that is, the graphs with no odd hole and no odd antihole) were called Berge graphs.[6]

The perfect graph theorem was proven by László Lovász in 1972,[1] who in the same year proved the stronger inequality between the number of vertices and the product of the clique number and independence number, without benefit of the strong perfect graph theorem.[3] In 1991, Alfred Lehman won Fulkerson Prize, sponsored jointly by the Mathematical Optimization Society and American Mathematical Society, for his work on generalizations of the theory of perfect graphs to logical matrices.[7] The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years,[6] until its proof was announced in 2002 by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas,[8] and published by them in 2006.[2] This work won its authors the 2009 Fulkerson Prize.[9] The perfect graph theorem has a short proof, but the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition of Berge graphs. Related decomposition techniques have also borne fruit in the study of other graph classes, and in particular for the claw-free graphs.[10] The symmetric characterization of perfect graphs in terms of the product of clique number and independence number was originally suggested by Hajnal and proven by Lovász.[3]

Families of graphs

Many well-studied families of graphs are perfect,[6] and in many cases the fact that these graphs are perfect corresponds to a minimax theorem for some kinds of combinatorial structure defined by these graphs. Examples of this phenomenon include the perfection of bipartite graphs and their line graphs, associated with Kőnig's theorem relating maximum matchings and vertex covers in bipartite graphs, and the perfection of comparability graphs, associated with Dilworth's theorem and Mirsky's theorem on chains and antichains in partially ordered sets. Other important classes of graphs, defined by having a structure related to the holes and antiholes of the strong perfect graph theorem, include the chordal graphs, Meyniel graphs, and their subclasses.

Bipartite graphs and line graphs

A bipartite graph (left) and its line graph (right). The shaded cliques in the line graph correspond to the vertices of the underlying bipartite graph, and have size equal to the degree of the corresponding vertex.

A bipartite graph is a graph that can be colored with two colors, or equivalently a graph that has no odd cycles. Because they have no odd cycles, they have no cliques of three or more vertices, so (when they have at least one edge) their chromatic number and clique number are both two. An induced subgraph of a bipartite graph remains bipartite, with the same equality between chromatic number and clique number, so the bipartite graphs are perfect.[6] They include as subclasses the trees, even-length cycle graphs, lattice graphs, knight's graphs, modular graphs, median graphs, and partial cubes, among many others.[11]

The perfect graph theorem, applied to bipartite graphs, produces a less-obvious equality: in these graphs, the size of the maximum independent set equals the size of the smallest clique cover. Because bipartite graphs are triangle-free, their minimum clique covers consist of a maximum matching (a set of disjoint edges, as many as possible) together with one-vertex cliques for all remaining vertices. And in any graph, the maximum independent set is complementary to a vertex cover, a set of vertices that touches all edges. Therefore, the equality of the maximum independent set and minimum clique cover can be expressed equivalently as an equality between the size of the maximum matching and the minimum vertex cover, the usual formulation of Kőnig's theorem.[12]

The same equality can be expressed in another way, involving a different class of perfect graphs. A matching, in any graph , is the same thing as an independent set in the line graph , a graph that has a vertex for each edge in . There is an edge between two vertices in whenever the corresponding two edges in share an endpoint. There are two kinds of cliques in a line graph : the ones coming from sets of edges in that all have a common endpoint, and the ones coming from triangles in . However, if is bipartite, only the first kind of clique can exist in . Therefore, in this case, a clique cover in corresponds to a vertex cover in , so in line graphs of bipartite graphs the independence number and clique cover number are equal. Induced subgraphs of line graphs of bipartite graphs remain in the same family (they correspond to the subgraphs of the underlying bipartite graph), and so the line graphs of bipartite graphs are perfect.[12] In particular this is true of the rook's graphs, the line graphs of complete bipartite graphs. Every line graph of a bipartite graph is an induced subgraph of a rook's graph.[13]

Because line graphs of bipartite graphs are perfect, their clique number equals their chromatic number. The clique number of the line graph of a bipartite graph is the maximum degree of any vertex of the underlying bipartite graph. The chromatic number of the line graph of a bipartite graph is the chromatic index of the underlying bipartite graph. It is the minimum number of colors needed to color the edges so that no two edges of the same color share an endpoint. Each color class forms a matching, so the chromatic index is also the minimum number of matchings needed to cover all of the edges of the graph. The equality of maximum degree and chromatic index, in bipartite graphs, is another theorem of Dénes Kőnig. In arbitrary simple graphs, they can differ by one; this is Vizing's theorem.[12]

A line perfect graph, with black bipartite biconnected components, blue , and red triangular books

If a line graph is perfect, the underlying graph is said to be a line perfect graph. The line perfect graphs are the graphs whose biconnected components are bipartite graphs, the complete graph , and triangular books, sets of triangles sharing an edge. Because these components are themselves perfect, and are combined in a way that preserves the property of being perfect, every line perfect graph is itself a perfect graph.[12]

Comparability graphs

The Hasse diagram of a partially ordered set, and its comparability graph

A partially ordered set is defined by its set of elements, and a comparison relation on these elements, obeying the requirements that ≤ is a reflexive relation (for all elements , ), an antisymmetric relation (if and , then , and a transitive relation (if and , then ). Two distinct elements and are said to be comparable if or , and incomparable otherwise. For instance, the set inclusion operation is the comparison relation of a partial order on any family of sets. The comparability graph of a partially ordered set is a graph with the set elements as its vertices, and with an edge connecting two vertices whenever those two elements are comparable. Its complement is called an incomparability graph. The comparability graph is not enough to uniquely identify a partial order; different partial orders may have the same comparability graph. For instance, reversing all comparison relations between pairs of elements changes their order but does not change their comparability graph.[14]

Finite comparability graphs (and their complementary incomparability graphs) are always perfect.[15] A clique, in a comparability graph, comes from a subset of elements that are all pairwise comparable; such a subset is called a chain, and it is linearly ordered by the given partial order. An independent set comes from a subset of elements no two of which are comparable; such a subset is called an antichain. Thus, a coloring of a comparability graph is a partition of its elements into antichains, and a clique cover is a partition of its elements into chains. Dilworth's theorem, in the theory of partial orders, states that for every finite partial order, the size of the largest antichain equals the minimum number of chains into which the elements can be partitioned. In the language of graphs, this can be stated as: every finite comparability graph is perfect. Similarly, Mirsky's theorem states that for every finite partial order, the size of the largest chain equals the minimum number of antichains into which the elements can be partitioned, or that every finite incomparability graph is perfect. These two theorems are equivalent via the perfect graph theorem, but Mirsky's theorem is easier than Dilworth's theorem to prove directly: if each element is labeled by the size of the largest chain in which it is maximal, then the subsets with equal labels form a partition into antichains, with the number of antichains equal to the size of the largest chain overall.[16]

Every bipartite graph is the comparability graph of a partial order. If a bipartite graph has its vertices colored, say red and blue, then it is the comparability graph for a comparison relation in which every red vertex is every blue vertex, every vertex is itself, and there are no other comparable pairs. In the partial orders constructed in this way, the largest chains consist of one red and one blue vertex. Thus, by connecting them through the theory of perfect graphs, Kőnig's theorem can be seen as a special case of Dilworth's theorem.[17]

The permutation graph of the permutation (4,3,5,1,2) connects pairs of elements whose ordering is reversed by the permutation.

A permutation graph is defined from a permutation on a totally ordered sequence of elements (conventionally, the integers from to ), which form the vertices of the graph. The edges of a permutation graph connect pairs of elements whose ordering is reversed by the given permutation. These are naturally incomparability graphs, for a partial order in which whenever occurs before in both the given sequence and its permutation. The complement of a permutation graph is another permutation graph, for the reverse of the given permutation. Therefore, as well as being incomparability graphs, permutation graphs are comparability graphs. In fact, the permutation graphs are exactly the graphs that are both comparability and incomparability graphs.[18] A clique, in a permutation graph, is a subsequence of elements that appear in increasing order in the given permutation, and an independent set is a subsequence of elements that appear in decreasing order. In any perfect graph, the product of the clique number and independence number are at least the number of vertices; the special case of this inequality for permutation graphs is the Erdős–Szekeres theorem.[16]

An interval graph and the intervals defining it

The interval graphs are the incomparability graphs of interval orders, orderings defined by sets of intervals on the real line with whenever interval is completely to the left of interval . In the corresponding interval graph, there is an edge from to whenever the two intervals have a point in common. Coloring these graphs can be used to model problems of assigning resources to tasks (such as classrooms to classes) with intervals describing the scheduled time of each task.[19] Both interval graphs and permutation graphs are generalized by the trapezoid graphs, the incomparability graphs of orderings defined in the same way for a system of trapezoids between two parallel lines, with whenever trapezoid is completely to the left of trapezoid .[20] Systems of intervals in which no two are nested produce a more restricted class of graphs, the indifference graphs, the incomparability graphs of semiorders. These have been used to model human preferences under the assumption that, when items have utilities that are very close to each other, they will be incomparable.[21] Another special case of the interval graphs is the family of trivially perfect graphs, formed from intervals where each two are either nested or disjoint.[22] These are the comparability graphs of ordered trees, and the graphs for which, in every induced subgraph, the independence number equals the number of maximal cliques.[23]

Incremental constructions

Several families of perfect graphs can be characterized by an incremental construction in which the graphs in the family are built up by adding one vertex at a time, according to certain rules, which guarantee that after each vertex is added the graph remains perfect.

  • The chordal graphs are the graphs formed by a construction of this type in which, at the time a vertex is added, its neighbors form a clique. The maximum clique in the graph is the largest clique obtained in this way from a newly added vertex and its neighbors. Chordal graphs may also be characterized as the graphs that have no holes (even or odd). They include as special cases the forests, the interval graphs, the maximal outerplanar graphs, and the split graphs in which the vertices can be partitioned into a clique and an independent set. The k-trees, central to the definition of treewidth, are chordal graphs in which all maximal cliques have the same size.
Three types of vertex addition in a distance-hereditary graph
  • The distance-hereditary graphs are formed, starting from a single-vertex graph, by repeatedly adding degree-one vertices ("pendant vertices") or copies of existing vertices (with the same neighbors). Each time a vertex is copied, the vertex and its copy may be adjacent (forming true twins) or non-adjacent (forming false twins). These graphs have the property that, in every connected induced subgraph, the distances between vertices are the same as in the whole graph. If only the twin operations are used, the result is a cograph. The cographs are the comparability graphs of series-parallel partial orders and can also be formed by a different construction process combining complementation and the disjoint union of graphs.
  • The graphs that are both chordal and distance-hereditary are called Ptolemaic graphs, because their distances obey Ptolemy's inequality. They have a restricted form of the distance-hereditary construction sequence, in which a false twin can only be added when its neighbors would form a clique. They include as special cases the windmill graphs consisting of cliques joined at a single vertex, and the block graphs in which each biconnected component is a clique.
  • The threshold graphs are formed from an empty graph by repeatedly adding either an isolated vertex (connected to nothing else) or a universal vertex (connected to all other vertices). They are special cases of the split graphs and the trivially perfect graphs, and are exactly the graphs that are both trivially perfect and the complement of a trivially perfect graph.

If the vertices of a chordal graph are colored in the order of an incremental construction sequence using a greedy coloring algorithm, the result will be an optimal coloring. The reverse of the vertex ordering used in this construction is called an elimination order. Similarly, if the vertices of a distance-hereditary graph are colored in the order of an incremental construction sequence, the resulting coloring will be optimal. If the vertices of a comparability graph are colored in the order of a linear extension of its underlying partial order, the resulting coloring will be optimal. This property is generalized in the family of perfectly orderable graphs, the graphs for which there exists an ordering that, when restricted to any induced subgraph, causes greedy coloring to be optimal. The cographs are exactly the graphs for which all vertex orderings have this property.

Other families

Many other classes of perfect graphs have been studied. For instance, the strongly perfect graphs are graphs in which, in every induced subgraph, there exists an independent set that intersects all maximal cliques. The Meyniel graphs have been called very strongly perfect because in them, every vertex belongs to such an independent set. The Meyniel graphs can also be defined as the graphs in which every odd cycle of length five or more has at least two chords.

A parity graph that is neither distance-hereditary nor bipartite

A parity graph is defined by the property that between every two vertices, all induced paths have the same parity: either they are all even in length, or they are all odd in length. This is true, for instance, of the distance-hereditary graphs, in which all induced paths between the same two vertices have the same length. It is also true of the bipartite graphs: in a bipartite graph, if two vertices are on the same side of the bipartition, then all paths between them have even length, and if they are on opposite sides then all paths between them have odd length. The parity graphs are a subclass of the Meyniel graphs: in any long odd cycle of a parity graph, at least two chords are needed to prevent the cycle being partitioned into two induced paths of different parity. The prism over any parity graph (its Cartesian product with a single edge) is another parity graph, and the parity graphs are the only graphs whose prisms are perfect.

Tolerance graphs are defined by specifying both an interval of the real line for each vertex and a non-negative real number, the tolerance of the vertex. Two vertices are adjacent whenever their intervals overlap for a length that is at least as large as the minimum of their two tolerances. Thus, the interval graphs are a special case of tolerance graphs, having tolerance zero. Like interval graphs, tolerance graphs can be used to model scheduling problems, where the tasks to be scheduled may only share resources for a short period of time (the tolerance of the tasks). The complements of tolerance graphs form a subclass of the perfectly orderable graphs.[24]

Structural decomposition

Algorithms

In all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time (Grötschel, Lovász & Schrijver 1988). The algorithm for the general case involves the Lovász number of these graphs, which (for the complement of a given graph) is sandwiched between the chromatic number and clique number. Calculating the Lovász number can be formulated as a semidefinite program and approximated numerically in polynomial time using the ellipsoid method for linear programming. For perfect graphs, rounding this approximation to an integer gives the chromatic number and clique number in polynomial time; the maximum independent set can be found by applying the same approach to the complement of the graph. However, this method is complicated and has a high polynomial exponent. More efficient combinatorial algorithms are known for many special cases.

For many years the complexity of recognizing Berge graphs and perfect graphs remained open. From the definition of Berge graphs, it follows immediately that their recognition is in co-NP (Lovász 1983). Finally, subsequent to the proof of the strong perfect graph theorem, a polynomial time algorithm was discovered by Chudnovsky, Cornuéjols, Liu, Seymour, and Vušković.

References

  1. ^ a b Lovász, László (1972). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics. 2 (3): 253–267. doi:10.1016/0012-365X(72)90006-4. MR 0302480. Zbl 0239.05111.
  2. ^ a b Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006). "The strong perfect graph theorem". Annals of Mathematics. 164 (1): 51–229. arXiv:math/0212070. doi:10.4007/annals.2006.164.51. MR 2233847. S2CID 119151552. Zbl 1112.05042.
  3. ^ a b c Lovász, László (1972). "A characterization of perfect graphs". Journal of Combinatorial Theory. Series B. 13 (2): 95–98. doi:10.1016/0095-8956(72)90045-7. MR 0309780. Zbl 0241.05107.
  4. ^ Gallai, Tibor (1958). "Maximum-minimum Sätze über Graphen". Acta Mathematica Academiae Scientiarum Hungaricae. 9 (3–4): 395–434. doi:10.1007/BF02020271. MR 0124238. S2CID 123953062. Zbl 0084.19603.
  5. ^ Berge, Claude (1963). "Perfect graphs". Six Papers on Graph Theory. Calcutta: Indian Statistical Institute. pp. 1–21.
  6. ^ a b c d Hougardy, Stefan (2006). "Classes of perfect graphs". Discrete Mathematics. 306 (19–20): 2529–2571. doi:10.1016/j.disc.2006.05.021. MR 2261918. Zbl 1104.05029.
  7. ^ "The 1991 D. R. Fulkerson Prizes in Discrete Mathematics" (PDF). 1991 Prize Recipients. Optima: Mathematical Optimization Society Newsletter (35): 4–8. November 1991. Retrieved 2023-01-21.
  8. ^ Mackenzie, Dana (July 5, 2002). "Mathematics: Graph theory uncovers the roots of perfection". Science. 297 (5578): 38. doi:10.1126/science.297.5578.38. PMID 12098683.
  9. ^ "2009 Fulkerson Prize Citation". Mathematical Optimization Society. Retrieved 2023-01-21.
  10. ^ Chudnovsky, Maria; Seymour, Paul (2005). "The structure of claw-free graphs" (PDF). Surveys in combinatorics 2005. Papers from the 20th British combinatorial conference, University of Durham, Durham, UK, July 10–15, 2005. Cambridge University Press. pp. 153–171. ISBN 0-521-61523-2. MR 2187738. Zbl 1109.05092.
  11. ^ "Bipartite graphs". Information System on Graph Classes and their Inclusions. Retrieved 2023-01-24.
  12. ^ a b c d Trotter, L. E., Jr. (1977). "Line perfect graphs". Mathematical Programming. 12 (2): 255–259. doi:10.1007/BF01593791. MR 0457293. Zbl 0366.05043.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  13. ^ Boros, E.; Gurvich, V. (2006). "Perfect graphs, kernels, and cores of cooperative games". Discrete Mathematics. 306 (19–20): 2336–2354. doi:10.1016/j.disc.2005.12.031. MR 2261906. Zbl 1103.05034.
  14. ^ Harzheim, Egbert (2005). "Comparability graphs". Ordered Sets. Advances in Mathematics. Vol. 7. New York: Springer. pp. 353–368. doi:10.1007/0-387-24222-8_12. ISBN 0-387-24219-8. MR 2127991. Zbl 1072.06001.
  15. ^ Berge, Claude (1967). "Some classes of perfect graphs". Graph Theory and Theoretical Physics. London: Academic Press. pp. 155–165. MR 0232694. Zbl 0203.26403.
  16. ^ a b Mirsky, Leon (1971). "A dual of Dilworth's decomposition theorem". The American Mathematical Monthly. 78 (8): 876–877. doi:10.2307/2316481. JSTOR 2316481. MR 0288054. Zbl 0263.06002.
  17. ^ Perfect, Hazel (1980). "Remarks on Dilworth's theorem in relation to transversal theory". Glasgow Mathematical Journal. 21 (1): 19–22. doi:10.1017/S0017089500003931. MR 0558270. Zbl 0428.06001.
  18. ^ Pnueli, A.; Lempel, A.; Even, S. (1971). "Transitive orientation of graphs and identification of permutation graphs". Canadian Journal of Mathematics. 23: 160–175. doi:10.4153/CJM-1971-016-5. MR 0292717. Zbl 0204.24604.
  19. ^ Kolen, Antoon W. J.; Lenstra, Jan Karel; Papadimitriou, Christos H.; Spieksma, Frits C. R. (2007). "Interval scheduling: a survey". Naval Research Logistics. 54 (5): 530–543. doi:10.1002/nav.20231. MR 2335544. Zbl 1143.90337.
  20. ^ Dagan, Ido; Golumbic, Martin Charles; Pinter, Ron Yair (1988). "Trapezoid graphs and their coloring". Discrete Applied Mathematics. 21 (1): 35–46. doi:10.1016/0166-218X(88)90032-7. MR 0953414. Zbl 0658.05067.
  21. ^ Roberts, Fred S. (1969). "Indifference graphs". Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). New York: Academic Press. pp. 139–146. MR 0252267. Zbl 0193.24205.
  22. ^ Skrien, Dale J. (1982). "A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs". Journal of Graph Theory. 6 (3): 309–316. doi:10.1002/jgt.3190060307. MR 0666799. Zbl 0495.05027.
  23. ^ Golumbic, Martin Charles (1978). "Trivially perfect graphs". Discrete Mathematics. 24 (1): 105–107. doi:10.1016/0012-365X(78)90178-4. MR 0522739. Zbl 0384.05057.
  24. ^ Golumbic, Martin Charles; Trenk, Ann N. (2004). Tolerance graphs. Cambridge Studies in Advanced Mathematics. Vol. 89. Cambridge University Press. doi:10.1017/CBO9780511542985. ISBN 0-521-82758-2. MR 2051713.

Bibliography

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Perfect_graph&oldid=1136215072"