Perfect graph theorem: Difference between revisions

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
VisualWikitext
imported>Vstephen B
mNo edit summary
 
imported>David Eppstein
math formatting
 
Line 1: Line 1:
{{Short description|An undirected graph is perfect if and only if its complement graph is also perfect}}
{{Short description|Complements of perfect graphs are perfect}}
[[File:Complementary perfect graphs.svg|thumb|upright=1.35|Two complementary perfect graphs]]
[[File:Complementary perfect graphs.svg|thumb|upright=1.35|Two complementary perfect graphs]]
In [[graph theory]], the '''perfect graph theorem''' of {{harvs|last=Lovász|first=László|authorlink=László Lovász|year=1972a|year2=1972b|txt}} states that an [[undirected graph]] is [[perfect graph|perfect]] if and only if its [[complement graph]] is also perfect. This result had been [[conjecture]]d by {{harvs|last=Berge|authorlink=Claude Berge|year=1961|year2=1963|txt}}, and it is sometimes called the weak perfect graph theorem to distinguish it from the [[strong perfect graph theorem]]<ref>This was also conjectured by Berge but only proven much later by {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}}.</ref> characterizing perfect graphs by their [[Forbidden graph characterization|forbidden induced subgraphs]].
In [[graph theory]], the '''perfect graph theorem''' of {{harvs|last=Lovász|first=László|authorlink=László Lovász|year=1972a|year2=1972b|txt}} states that an [[undirected graph]] is [[perfect graph|perfect]] if and only if its [[complement graph]] is also perfect. This result had been [[conjecture]]d by {{harvs|last=Berge|authorlink=Claude Berge|year=1961|year2=1963|txt}}, and it is sometimes called the weak perfect graph theorem to distinguish it from the [[strong perfect graph theorem]]<ref>This was also conjectured by Berge but only proven much later by {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}}.</ref> characterizing perfect graphs by their [[Forbidden graph characterization|forbidden induced subgraphs]].
Line 16: Line 16:
==Example==
==Example==
[[File:7-hole and antihole.svg|thumb|240px|A 7-vertex cycle and its complement, the {{nowrap|7-vertex}} antihole, 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.]]
[[File:7-hole and antihole.svg|thumb|240px|A 7-vertex cycle and its complement, the {{nowrap|7-vertex}} antihole, 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.]]
Let ''G'' be a [[cycle graph]] of [[parity (mathematics)|odd]] length greater than three (a so-called "odd hole"). Then ''G'' requires at least three colors in any coloring, but has no triangle, so it is not perfect. By the perfect graph theorem, the complement of ''G'' (an "odd antihole") must therefore also not be perfect. If ''G'' is a cycle of five vertices, it is [[self-complementary graph|isomorphic to its complement]], but this property is not true for longer odd cycles, and it is not as trivial to compute the clique number and chromatic number in an odd antihole as it is in an odd hole. As the [[strong perfect graph theorem]] states, the odd holes and odd antiholes turn out to be the minimal [[Forbidden graph characterization|forbidden induced subgraphs]] for the perfect graphs.
Let <math>G</math> be a [[cycle graph]] of [[parity (mathematics)|odd]] length greater than three (a so-called "odd hole"). Then <math>G</math> requires at least three colors in any coloring, but has no triangle, so it is not perfect. By the perfect graph theorem, the complement of <math>G</math> (an "odd antihole") must therefore also not be perfect. If <math>G</math> is a cycle of five vertices, it is [[self-complementary graph|isomorphic to its complement]], but this property is not true for longer odd cycles, and it is not as trivial to compute the clique number and chromatic number in an odd antihole as it is in an odd hole. As the [[strong perfect graph theorem]] states, the odd holes and odd antiholes turn out to be the minimal [[Forbidden graph characterization|forbidden induced subgraphs]] for the perfect graphs.


==Applications==
==Applications==
In a nontrivial bipartite graph, the optimal number of colors is (by definition) two, and (since bipartite graphs are [[triangle-free graph|triangle-free]]) the maximum clique size is also two. Also, any induced subgraph of a bipartite graph remains bipartite. Therefore, bipartite graphs are perfect. In {{nowrap|''n''-vertex}} bipartite graphs, a minimum clique cover takes the form of a [[maximum matching]] together with an additional clique for every unmatched vertex, with size ''n''&nbsp;−&nbsp;''M'', where ''M'' is the cardinality of the matching. Thus, in this case, the perfect graph theorem implies [[Kőnig's theorem (graph theory)|Kőnig's theorem]] that the size of a maximum independent set in a bipartite graph is also ''n''&nbsp;−&nbsp;''M'',<ref>{{harvtxt|Kőnig|1931}}, later rediscovered by {{harvtxt|Gallai|1958}}.</ref> a result that was a major inspiration for Berge's formulation of the theory of perfect graphs.
In a nontrivial bipartite graph, the optimal number of colors is (by definition) two, and (since bipartite graphs are [[triangle-free graph|triangle-free]]) the maximum clique size is also two. Also, any induced subgraph of a bipartite graph remains bipartite. Therefore, bipartite graphs are perfect. In {{nowrap|<math>n</math>-vertex}} bipartite graphs, a minimum clique cover takes the form of a [[maximum matching]] together with an additional clique for every unmatched vertex, with size <math>n-M</math>, where <math>M</math> is the cardinality of the matching. Thus, in this case, the perfect graph theorem implies [[Kőnig's theorem (graph theory)|Kőnig's theorem]] that the size of a maximum independent set in a bipartite graph is {{nowrap|also <math>n-M</math>,<ref>{{harvtxt|Kőnig|1931}}, later rediscovered by {{harvtxt|Gallai|1958}}.</ref>}} a result that was a major inspiration for Berge's formulation of the theory of perfect graphs.


[[Mirsky's theorem]] characterizing the height of a [[partially ordered set]] in terms of partitions into [[antichain]]s can be formulated as the perfection of the [[comparability graph]] of the partially ordered set, and [[Dilworth's theorem]] characterizing the width of a partially ordered set in terms of partitions into chains can be formulated as the perfection of the complements of these graphs. Thus, the perfect graph theorem can be used to [[mathematical proof|prove]] Dilworth's theorem from the (much easier) proof of Mirsky's theorem, or vice versa.<ref>{{harvtxt|Golumbic|1980}}, Section 5.7, "Coloring and other problems on comparability graphs", pp. 132–135.</ref>
[[Mirsky's theorem]] characterizing the height of a [[partially ordered set]] in terms of partitions into [[antichain]]s can be formulated as the perfection of the [[comparability graph]] of the partially ordered set, and [[Dilworth's theorem]] characterizing the width of a partially ordered set in terms of partitions into chains can be formulated as the perfection of the complements of these graphs. Thus, the perfect graph theorem can be used to [[mathematical proof|prove]] Dilworth's theorem from the (much easier) proof of Mirsky's theorem, or vice versa.<ref>{{harvtxt|Golumbic|1980}}, Section 5.7, "Coloring and other problems on comparability graphs", pp. 132–135.</ref>


==Lovász's proof==
==Lovász's proof==
To prove the perfect graph theorem, Lovász used an operation of replacing vertices in a graph by cliques; it was already known to Berge that, if a graph is perfect, the graph formed by this replacement process is also perfect.<ref>See {{harvtxt|Golumbic|1980}}, Lemma 3.1(i), and {{harvtxt|Reed|2001}}, Corollary 2.21.</ref> Any such replacement process may be broken down into repeated steps of doubling a vertex. If the doubled vertex belongs to a maximum clique of the graph, it increases both the clique number and the chromatic number by one. If, on the other hand, the doubled vertex does not belong to a maximum clique, form a graph ''H'' by removing the vertices with the same color as the doubled vertex (but not the doubled vertex itself) from an optimal coloring of the given graph. The removed vertices meet every maximum clique, so ''H'' has clique number and chromatic number one less than that of the given graph. The removed vertices and the new copy of the doubled vertex can then be added back as a single color class, showing that in this case the doubling step leaves the chromatic number unchanged. The same argument shows that doubling preserves the equality of the clique number and the chromatic number in every induced subgraph of the given graph, so each doubling step preserves the perfection of the graph.<ref>{{harvtxt|Reed|2001}}, Lemma 2.20.</ref>
To prove the perfect graph theorem, Lovász used an operation of replacing vertices in a graph by cliques; it was already known to Berge that, if a graph is perfect, the graph formed by this replacement process is also perfect.<ref>See {{harvtxt|Golumbic|1980}}, Lemma 3.1(i), and {{harvtxt|Reed|2001}}, Corollary 2.21.</ref> Any such replacement process may be broken down into repeated steps of doubling a vertex. If the doubled vertex belongs to a maximum clique of the graph, it increases both the clique number and the chromatic number by one. If, on the other hand, the doubled vertex does not belong to a maximum clique, form a graph <math>H</math> by removing the vertices with the same color as the doubled vertex (but not the doubled vertex itself) from an optimal coloring of the given graph. The removed vertices meet every maximum clique, so <math>H</math> has clique number and chromatic number one less than that of the given graph. The removed vertices and the new copy of the doubled vertex can then be added back as a single color class, showing that in this case the doubling step leaves the chromatic number unchanged. The same argument shows that doubling preserves the equality of the clique number and the chromatic number in every induced subgraph of the given graph, so each doubling step preserves the perfection of the graph.<ref>{{harvtxt|Reed|2001}}, Lemma 2.20.</ref>


Given a perfect graph ''G'', Lovász forms a graph ''G''* by replacing each vertex ''v'' by a clique of ''t<sub>v</sub>'' vertices, where ''t<sub>v</sub>'' is the number of distinct maximum independent sets in ''G'' that contain ''v''. It is possible to correspond each of the distinct maximum independent sets in ''G'' with one of the maximum independent sets in ''G''*, in such a way that the chosen maximum independent sets in ''G''* are all [[disjoint sets|disjoint]] and each vertex of ''G''* appears in a single chosen set; that is, ''G''* has a coloring in which each color class is a maximum independent set. Necessarily, this coloring is an optimal coloring of ''G''*. Because ''G'' is perfect, so is ''G''*, and therefore it has a maximum clique ''K''* whose size equals the number of colors in this coloring, which is the number of distinct maximum independent sets in ''G''; necessarily, ''K''* contains a distinct representative for each of these maximum independent sets. The corresponding set ''K'' of vertices in ''G'' (the vertices whose expanded cliques in ''G''* intersect ''K''*) is a clique in ''G'' with the property that it intersects every maximum independent set in ''G''. Therefore, the graph formed from ''G'' by removing ''K'' has clique cover number at most one less than the clique number of ''G'', and independence number at least one less than the independence number of ''G'', and the result follows by [[mathematical induction|induction]] on this number.<ref>We follow here the exposition of the proof by {{harvtxt|Reed|2001}}. {{harvtxt|Golumbic|1980}} notes that much of this line of reasoning was quickly reconstructed by [[D. R. Fulkerson]] after hearing of Lovász's result but not seeing his proof.</ref>
Given a perfect graph <math>G</math>, Lovász forms a graph <math>G^*</math> by replacing each vertex <math>v</math> by a clique of <math>t_v</math> vertices, where <math>t_v</math> is the number of distinct maximum independent sets in <math>G</math> that contain <math>v</math>. It is possible to correspond each of the distinct maximum independent sets in <math>G</math> with one of the maximum independent sets in <math>G^*</math>, in such a way that the chosen maximum independent sets in <math>G^*</math> are all [[disjoint sets|disjoint]] and each vertex of <math>G^*</math> appears in a single chosen set; that is, <math>G^*</math> has a coloring in which each color class is a maximum independent set. Necessarily, this coloring is an optimal coloring of <math>G^*</math>. Because <math>G</math> is perfect, so is <math>G^*</math>, and therefore it has a maximum clique <math>K^*</math> whose size equals the number of colors in this coloring, which is the number of distinct maximum independent sets in <math>G</math>; necessarily, <math>K^*</math> contains a distinct representative for each of these maximum independent sets. The corresponding set <math>K</math> of vertices in <math>G</math> (the vertices whose expanded cliques in <math>G^*</math> intersect <math>K^*</math>) is a clique in <math>G</math> with the property that it intersects every maximum independent set in <math>G</math>. Therefore, the graph formed from <math>G</math> by removing <math>K</math> has clique cover number at most one less than the clique number of <math>G</math>, and independence number at least one less than the independence number of <math>G</math>, and the result follows by [[mathematical induction|induction]] on this number.<ref>We follow here the exposition of the proof by {{harvtxt|Reed|2001}}. {{harvtxt|Golumbic|1980}} notes that much of this line of reasoning was quickly reconstructed by [[D. R. Fulkerson]] after hearing of Lovász's result but not seeing his proof.</ref>


==Relation to the strong perfect graph theorem==
==Relation to the strong perfect graph theorem==

Latest revision as of 19:48, 29 June 2025

Template:Short description

File:Complementary perfect graphs.svg
Two complementary perfect graphs

In graph theory, the perfect graph theorem of Template:Harvs states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Template:Harvs, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem[1] characterizing perfect graphs by their forbidden induced subgraphs.

Statement

A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph. Perfect graphs include many important graphs classes including bipartite graphs, chordal graphs, and comparability graphs.

The complement of a graph has an edge between two vertices if and only if the original graph does not have an edge between the same two vertices. Thus, a clique in the original graph becomes an independent set in the complement and a coloring of the original graph becomes a clique cover of the complement.

The perfect graph theorem states:

The complement of a perfect graph is perfect.

Equivalently, in a perfect graph, the size of the maximum independent set equals the minimum number of cliques in a clique cover.

Example

File:7-hole and antihole.svg
A 7-vertex cycle and its complement, the 7-vertex antihole, 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.

Let G be a cycle graph of odd length greater than three (a so-called "odd hole"). Then G requires at least three colors in any coloring, but has no triangle, so it is not perfect. By the perfect graph theorem, the complement of G (an "odd antihole") must therefore also not be perfect. If G is a cycle of five vertices, it is isomorphic to its complement, but this property is not true for longer odd cycles, and it is not as trivial to compute the clique number and chromatic number in an odd antihole as it is in an odd hole. As the strong perfect graph theorem states, the odd holes and odd antiholes turn out to be the minimal forbidden induced subgraphs for the perfect graphs.

Applications

In a nontrivial bipartite graph, the optimal number of colors is (by definition) two, and (since bipartite graphs are triangle-free) the maximum clique size is also two. Also, any induced subgraph of a bipartite graph remains bipartite. Therefore, bipartite graphs are perfect. In n-vertex bipartite graphs, a minimum clique cover takes the form of a maximum matching together with an additional clique for every unmatched vertex, with size n−M, where M is the cardinality of the matching. Thus, in this case, the perfect graph theorem implies Kőnig's theorem that the size of a maximum independent set in a bipartite graph is also n−M,[2] a result that was a major inspiration for Berge's formulation of the theory of perfect graphs.

Mirsky's theorem characterizing the height of a partially ordered set in terms of partitions into antichains can be formulated as the perfection of the comparability graph of the partially ordered set, and Dilworth's theorem characterizing the width of a partially ordered set in terms of partitions into chains can be formulated as the perfection of the complements of these graphs. Thus, the perfect graph theorem can be used to prove Dilworth's theorem from the (much easier) proof of Mirsky's theorem, or vice versa.[3]

Lovász's proof

To prove the perfect graph theorem, Lovász used an operation of replacing vertices in a graph by cliques; it was already known to Berge that, if a graph is perfect, the graph formed by this replacement process is also perfect.[4] Any such replacement process may be broken down into repeated steps of doubling a vertex. If the doubled vertex belongs to a maximum clique of the graph, it increases both the clique number and the chromatic number by one. If, on the other hand, the doubled vertex does not belong to a maximum clique, form a graph H by removing the vertices with the same color as the doubled vertex (but not the doubled vertex itself) from an optimal coloring of the given graph. The removed vertices meet every maximum clique, so H has clique number and chromatic number one less than that of the given graph. The removed vertices and the new copy of the doubled vertex can then be added back as a single color class, showing that in this case the doubling step leaves the chromatic number unchanged. The same argument shows that doubling preserves the equality of the clique number and the chromatic number in every induced subgraph of the given graph, so each doubling step preserves the perfection of the graph.[5]

Given a perfect graph G, Lovász forms a graph G* by replacing each vertex v by a clique of tv vertices, where tv is the number of distinct maximum independent sets in G that contain v. It is possible to correspond each of the distinct maximum independent sets in G with one of the maximum independent sets in G*, in such a way that the chosen maximum independent sets in G* are all disjoint and each vertex of G* appears in a single chosen set; that is, G* has a coloring in which each color class is a maximum independent set. Necessarily, this coloring is an optimal coloring of G*. Because G is perfect, so is G*, and therefore it has a maximum clique K* whose size equals the number of colors in this coloring, which is the number of distinct maximum independent sets in G; necessarily, K* contains a distinct representative for each of these maximum independent sets. The corresponding set K of vertices in G (the vertices whose expanded cliques in G* intersect K*) is a clique in G with the property that it intersects every maximum independent set in G. Therefore, the graph formed from G by removing K has clique cover number at most one less than the clique number of G, and independence number at least one less than the independence number of G, and the result follows by induction on this number.[6]

Relation to the strong perfect graph theorem

The strong perfect graph theorem of Template:Harvtxt states that a graph is perfect if and only if none of its induced subgraphs are cycles of odd length greater than or equal to five, or their complements. Because this characterization is unaffected by graph complementation, it immediately implies the weak perfect graph theorem.

Generalizations

Template:Harvtxt proved that, if the edges of a complete graph are partitioned into three subgraphs in such a way that every three vertices induce a connected graph in one of the three subgraphs, and if two of the subgraphs are perfect, then the third subgraph is also perfect. The perfect graph theorem is the special case of this result when one of the three subgraphs is the empty graph.

Notes

Template:Reflist

References

  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1".
  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1".
  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1"..
  • Script error: No such module "citation/CS1"..
  1. ↑ This was also conjectured by Berge but only proven much later by Template:Harvtxt.
  2. ↑ Template:Harvtxt, later rediscovered by Template:Harvtxt.
  3. ↑ Template:Harvtxt, Section 5.7, "Coloring and other problems on comparability graphs", pp. 132–135.
  4. ↑ See Template:Harvtxt, Lemma 3.1(i), and Template:Harvtxt, Corollary 2.21.
  5. ↑ Template:Harvtxt, Lemma 2.20.
  6. ↑ We follow here the exposition of the proof by Template:Harvtxt. Template:Harvtxt notes that much of this line of reasoning was quickly reconstructed by D. R. Fulkerson after hearing of Lovász's result but not seeing his proof.
Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Perfect_graph_theorem&oldid=2025994"