fbpx
Wikipedia

Strong perfect graph theorem

January 14, 2023

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes (odd-length induced cycles of length at least 5) nor odd antiholes (complements of odd holes). It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002[1] and published by them in 2006.

The proof of the strong perfect graph theorem won for its authors a $10,000 prize offered by Gérard Cornuéjols of Carnegie Mellon University[2] and the 2009 Fulkerson Prize.[3]

Statement

A perfect graph is a graph in which, for every induced subgraph, the size of the maximum clique equals the minimum number of colors in a coloring of the graph; perfect graphs include many well-known graph classes including the bipartite graphs, chordal graphs, and comparability graphs. In his 1961 and 1963 works defining for the first time this class of graphs, Claude Berge observed that it is impossible for a perfect graph to contain an odd hole, an induced subgraph in the form of an odd-length cycle graph of length five or more, because odd holes have clique number two and chromatic number three. Similarly, he observed that perfect graphs cannot contain odd antiholes, induced subgraphs complementary to odd holes: an odd antihole with 2k + 1 vertices has clique number k and chromatic number k + 1, which is again impossible for perfect graphs. The graphs having neither odd holes nor odd antiholes became known as the Berge graphs.

Berge conjectured that every Berge graph is perfect, or equivalently that the perfect graphs and the Berge graphs define the same class of graphs. This became known as the strong perfect graph conjecture, until its proof in 2002, when it was renamed the strong perfect graph theorem.

Relation to the weak perfect graph theorem

Another conjecture of Berge, proved in 1972 by László Lovász, is that the complement of every perfect graph is also perfect. This became known as the perfect graph theorem, or (to distinguish it from the strong perfect graph conjecture/theorem) the weak perfect graph theorem. Because Berge's forbidden graph characterization is self-complementary, the weak perfect graph theorem follows immediately from the strong perfect graph theorem.

Proof ideas

The proof of the strong perfect graph theorem by Chudnovsky et al. follows an outline conjectured in 2001 by Conforti, Cornuéjols, Robertson, Seymour, and Thomas, according to which every Berge graph either forms one of five types of basic building block (special classes of perfect graphs) or it has one of four different types of structural decomposition into simpler graphs. A minimally imperfect Berge graph cannot have any of these decompositions, from which it follows that no counterexample to the theorem can exist.[4] This idea was based on previous conjectured structural decompositions of similar type that would have implied the strong perfect graph conjecture but turned out to be false.[5]

The five basic classes of perfect graphs that form the base case of this structural decomposition are the bipartite graphs, line graphs of bipartite graphs, complementary graphs of bipartite graphs, complements of line graphs of bipartite graphs, and double split graphs. It is easy to see that bipartite graphs are perfect: in any nontrivial induced subgraph, the clique number and chromatic number are both two and therefore both equal. The perfection of complements of bipartite graphs, and of complements of line graphs of bipartite graphs, are both equivalent to Kőnig's theorem relating the sizes of maximum matchings, maximum independent sets, and minimum vertex covers in bipartite graphs. The perfection of line graphs of bipartite graphs can be stated equivalently as the fact that bipartite graphs have chromatic index equal to their maximum degree, proven by Kőnig (1916). Thus, all four of these basic classes are perfect. The double split graphs are a relative of the split graphs that can also be shown to be perfect.[6]

The four types of decompositions considered in this proof are 2-joins, complements of 2-joins, balanced skew partitions, and homogeneous pairs.

A 2-join is a partition of the vertices of a graph into two subsets, with the property that the edges spanning the cut between these two subsets form two vertex-disjoint complete bipartite graphs. When a graph has a 2-join, it may be decomposed into induced subgraphs called "blocks", by replacing one of the two subsets of vertices by a shortest path within that subset that connects one of the two complete bipartite graphs to the other; when no such path exists, the block is formed instead by replacing one of the two subsets of vertices by two vertices, one for each complete bipartite subgraph. A 2-join is perfect if and only if its two blocks are both perfect. Therefore, if a minimally imperfect graph has a 2-join, it must equal one of its blocks, from which it follows that it must be an odd cycle and not Berge. For the same reason, a minimally imperfect graph whose complement has a 2-join cannot be Berge.[7]

A skew partition is a partition of a graph's vertices into two subsets, one of which induces a disconnected subgraph and the other of which has a disconnected complement; Chvátal (1985) had conjectured that no minimal counterexample to the strong perfect graph conjecture could have a skew partition. Chudnovsky et al. introduced some technical constraints on skew partitions, and were able to show that Chvátal's conjecture is true for the resulting "balanced skew partitions". The full conjecture is a corollary of the strong perfect graph theorem.[8]

A homogeneous pair is related to a modular decomposition of a graph. It is a partition of the graph into three subsets V1, V2, and V3 such that V1 and V2 together contain at least three vertices, V3 contains at least two vertices, and for each vertex v in V3 and each i in {1,2} either v is adjacent to all vertices in Vi or to none of them. It is not possible for a minimally imperfect graph to have a homogeneous pair.[9] Subsequent to the proof of the strong perfect graph conjecture, Chudnovsky (2006) simplified it by showing that homogeneous pairs could be eliminated from the set of decompositions used in the proof.

The proof that every Berge graph falls into one of the five basic classes or has one of the four types of decomposition follows a case analysis, according to whether certain configurations exist within the graph: a "stretcher", a subgraph that can be decomposed into three induced paths subject to certain additional constraints, the complement of a stretcher, and a "proper wheel", a configuration related to a wheel graph, consisting of an induced cycle together with a hub vertex adjacent to at least three cycle vertices and obeying several additional constraints. For each possible choice of whether a stretcher or its complement or a proper wheel exists within the given Berge graph, the graph can be shown to be in one of the basic classes or to be decomposable.[10] This case analysis completes the proof.

Notes

  1. ^ Mackenzie (2002); Cornuéjols (2002).
  2. ^ Mackenzie (2002).
  3. ^ "2009 Fulkerson Prizes" (PDF), Notices of the American Mathematical Society: 1475–1476, December 2011.
  4. ^ Cornuéjols (2002), Conjecture 5.1.
  5. ^ Reed (1986); Hougardy (1991); Rusu (1997); Roussel, Rusu & Thuillier (2009), section 4.6 "The first conjectures".
  6. ^ Roussel, Rusu & Thuillier (2009), Definition 4.39.
  7. ^ Cornuéjols & Cunningham (1985); Cornuéjols (2002), Theorem 3.2 and Corollary 3.3.
  8. ^ Seymour (2006); Roussel, Rusu & Thuillier (2009), section 4.7 "The skew partition"; Cornuéjols (2002), Theorems 4.1 and 4.2.
  9. ^ Chvátal & Sbihi (1987); Cornuéjols (2002), Theorem 4.10.
  10. ^ Cornuéjols (2002), Theorems 5.4, 5.5, and 5.6; Roussel, Rusu & Thuillier (2009), Theorem 4.42.

References

  • Berge, Claude (1961), "Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 114.
  • Berge, Claude (1963), "Perfect graphs", Six Papers on Graph Theory, Calcutta: Indian Statistical Institute, pp. 1–21.
  • Chudnovsky, Maria (2006), "Berge trigraphs", Journal of Graph Theory, 53 (1): 1–55, doi:10.1002/jgt.20165, MR 2245543.
  • 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.
  • Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2003), "Progress on perfect graphs", Mathematical Programming, Series B., 97 (1–2): 405–422, CiteSeerX 10.1.1.137.3013, doi:10.1007/s10107-003-0449-8, MR 2004404.
  • Chvátal, Václav (1985), "Star-cutsets and perfect graphs", Journal of Combinatorial Theory, Series B, 39 (3): 189–199, doi:10.1016/0095-8956(85)90049-8, MR 0815391.
  • Chvátal, Václav; Sbihi, Najiba (1987), "Bull-free Berge graphs are perfect", Graphs and Combinatorics, 3 (2): 127–139, doi:10.1007/BF01788536, MR 0932129.
  • Cornuéjols, Gérard (2002), "The strong perfect graph conjecture", Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002) (PDF), Beijing: Higher Ed. Press, pp. 547–559, MR 1957560.
  • Cornuéjols, G.; Cunningham, W. H. (1985), "Compositions for perfect graphs", Discrete Mathematics, 55 (3): 245–254, doi:10.1016/S0012-365X(85)80001-7, MR 0802663.
  • Hougardy, S. (1991), Counterexamples to three conjectures concerning perfect graphs, Technical Report RR870-M, Grenoble, France: Laboratoire Artemis-IMAG, Universitá Joseph Fourier. As cited by Roussel, Rusu & Thuillier (2009).
  • Kőnig, Dénes (1916), "Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére", Matematikai és Természettudományi Értesítő, 34: 104–119.
  • Lovász, László (1972a), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4.
  • Lovász, László (1972b), "A characterization of perfect graphs", Journal of Combinatorial Theory, Series B, 13 (2): 95–98, doi:10.1016/0095-8956(72)90045-7.
  • 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.
  • Reed, B. A. (1986), A semi-strong perfect graph theorem, Ph.D. thesis, Montréal, Québec, Canada: Department of Computer Science, McGill University. As cited by Roussel, Rusu & Thuillier (2009).
  • Roussel, F.; Rusu, I.; Thuillier, H. (2009), "The strong perfect graph conjecture: 40 years of attempts, and its resolution", Discrete Mathematics, 309 (20): 6092–6113, doi:10.1016/j.disc.2009.05.024, MR 2552645.
  • Rusu, Irena (1997), "Building counterexamples", Discrete Mathematics, 171 (1–3): 213–227, doi:10.1016/S0012-365X(96)00081-7, MR 1454452.
  • Seymour, Paul (2006), "How the proof of the strong perfect graph conjecture was found" (PDF), Gazette des Mathématiciens (109): 69–83, MR 2245898.

External links

January 14, 2023
strong, perfect, graph, theorem, graph, theory, strong, perfect, graph, theorem, forbidden, graph, characterization, perfect, graphs, being, exactly, graphs, that, have, neither, holes, length, induced, cycles, length, least, antiholes, complements, holes, con. In graph theory the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes odd length induced cycles of length at least 5 nor odd antiholes complements of odd holes It was conjectured by Claude Berge in 1961 A proof by Maria Chudnovsky Neil Robertson Paul Seymour and Robin Thomas was announced in 2002 1 and published by them in 2006 The proof of the strong perfect graph theorem won for its authors a 10 000 prize offered by Gerard Cornuejols of Carnegie Mellon University 2 and the 2009 Fulkerson Prize 3 Contents 1 Statement 2 Relation to the weak perfect graph theorem 3 Proof ideas 4 Notes 5 References 6 External linksStatement EditA perfect graph is a graph in which for every induced subgraph the size of the maximum clique equals the minimum number of colors in a coloring of the graph perfect graphs include many well known graph classes including the bipartite graphs chordal graphs and comparability graphs In his 1961 and 1963 works defining for the first time this class of graphs Claude Berge observed that it is impossible for a perfect graph to contain an odd hole an induced subgraph in the form of an odd length cycle graph of length five or more because odd holes have clique number two and chromatic number three Similarly he observed that perfect graphs cannot contain odd antiholes induced subgraphs complementary to odd holes an odd antihole with 2k 1 vertices has clique number k and chromatic number k 1 which is again impossible for perfect graphs The graphs having neither odd holes nor odd antiholes became known as the Berge graphs Berge conjectured that every Berge graph is perfect or equivalently that the perfect graphs and the Berge graphs define the same class of graphs This became known as the strong perfect graph conjecture until its proof in 2002 when it was renamed the strong perfect graph theorem Relation to the weak perfect graph theorem EditAnother conjecture of Berge proved in 1972 by Laszlo Lovasz is that the complement of every perfect graph is also perfect This became known as the perfect graph theorem or to distinguish it from the strong perfect graph conjecture theorem the weak perfect graph theorem Because Berge s forbidden graph characterization is self complementary the weak perfect graph theorem follows immediately from the strong perfect graph theorem Proof ideas EditThe proof of the strong perfect graph theorem by Chudnovsky et al follows an outline conjectured in 2001 by Conforti Cornuejols Robertson Seymour and Thomas according to which every Berge graph either forms one of five types of basic building block special classes of perfect graphs or it has one of four different types of structural decomposition into simpler graphs A minimally imperfect Berge graph cannot have any of these decompositions from which it follows that no counterexample to the theorem can exist 4 This idea was based on previous conjectured structural decompositions of similar type that would have implied the strong perfect graph conjecture but turned out to be false 5 The five basic classes of perfect graphs that form the base case of this structural decomposition are the bipartite graphs line graphs of bipartite graphs complementary graphs of bipartite graphs complements of line graphs of bipartite graphs and double split graphs It is easy to see that bipartite graphs are perfect in any nontrivial induced subgraph the clique number and chromatic number are both two and therefore both equal The perfection of complements of bipartite graphs and of complements of line graphs of bipartite graphs are both equivalent to Konig s theorem relating the sizes of maximum matchings maximum independent sets and minimum vertex covers in bipartite graphs The perfection of line graphs of bipartite graphs can be stated equivalently as the fact that bipartite graphs have chromatic index equal to their maximum degree proven by Konig 1916 Thus all four of these basic classes are perfect The double split graphs are a relative of the split graphs that can also be shown to be perfect 6 The four types of decompositions considered in this proof are 2 joins complements of 2 joins balanced skew partitions and homogeneous pairs A 2 join is a partition of the vertices of a graph into two subsets with the property that the edges spanning the cut between these two subsets form two vertex disjoint complete bipartite graphs When a graph has a 2 join it may be decomposed into induced subgraphs called blocks by replacing one of the two subsets of vertices by a shortest path within that subset that connects one of the two complete bipartite graphs to the other when no such path exists the block is formed instead by replacing one of the two subsets of vertices by two vertices one for each complete bipartite subgraph A 2 join is perfect if and only if its two blocks are both perfect Therefore if a minimally imperfect graph has a 2 join it must equal one of its blocks from which it follows that it must be an odd cycle and not Berge For the same reason a minimally imperfect graph whose complement has a 2 join cannot be Berge 7 A skew partition is a partition of a graph s vertices into two subsets one of which induces a disconnected subgraph and the other of which has a disconnected complement Chvatal 1985 had conjectured that no minimal counterexample to the strong perfect graph conjecture could have a skew partition Chudnovsky et al introduced some technical constraints on skew partitions and were able to show that Chvatal s conjecture is true for the resulting balanced skew partitions The full conjecture is a corollary of the strong perfect graph theorem 8 A homogeneous pair is related to a modular decomposition of a graph It is a partition of the graph into three subsets V1 V2 and V3 such that V1 and V2 together contain at least three vertices V3 contains at least two vertices and for each vertex v in V3 and each i in 1 2 either v is adjacent to all vertices in Vi or to none of them It is not possible for a minimally imperfect graph to have a homogeneous pair 9 Subsequent to the proof of the strong perfect graph conjecture Chudnovsky 2006 simplified it by showing that homogeneous pairs could be eliminated from the set of decompositions used in the proof The proof that every Berge graph falls into one of the five basic classes or has one of the four types of decomposition follows a case analysis according to whether certain configurations exist within the graph a stretcher a subgraph that can be decomposed into three induced paths subject to certain additional constraints the complement of a stretcher and a proper wheel a configuration related to a wheel graph consisting of an induced cycle together with a hub vertex adjacent to at least three cycle vertices and obeying several additional constraints For each possible choice of whether a stretcher or its complement or a proper wheel exists within the given Berge graph the graph can be shown to be in one of the basic classes or to be decomposable 10 This case analysis completes the proof Notes Edit Mackenzie 2002 Cornuejols 2002 Mackenzie 2002 2009 Fulkerson Prizes PDF Notices of the American Mathematical Society 1475 1476 December 2011 Cornuejols 2002 Conjecture 5 1 Reed 1986 Hougardy 1991 Rusu 1997 Roussel Rusu amp Thuillier 2009 section 4 6 The first conjectures Roussel Rusu amp Thuillier 2009 Definition 4 39 Cornuejols amp Cunningham 1985 Cornuejols 2002 Theorem 3 2 and Corollary 3 3 Seymour 2006 Roussel Rusu amp Thuillier 2009 section 4 7 The skew partition Cornuejols 2002 Theorems 4 1 and 4 2 Chvatal amp Sbihi 1987 Cornuejols 2002 Theorem 4 10 Cornuejols 2002 Theorems 5 4 5 5 and 5 6 Roussel Rusu amp Thuillier 2009 Theorem 4 42 References EditBerge Claude 1961 Farbung von Graphen deren samtliche bzw deren ungerade Kreise starr sind Wiss Z Martin Luther Univ Halle Wittenberg Math Natur Reihe 10 114 Berge Claude 1963 Perfect graphs Six Papers on Graph Theory Calcutta Indian Statistical Institute pp 1 21 Chudnovsky Maria 2006 Berge trigraphs Journal of Graph Theory 53 1 1 55 doi 10 1002 jgt 20165 MR 2245543 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 Chudnovsky Maria Robertson Neil Seymour Paul Thomas Robin 2003 Progress on perfect graphs Mathematical Programming Series B 97 1 2 405 422 CiteSeerX 10 1 1 137 3013 doi 10 1007 s10107 003 0449 8 MR 2004404 Chvatal Vaclav 1985 Star cutsets and perfect graphs Journal of Combinatorial Theory Series B 39 3 189 199 doi 10 1016 0095 8956 85 90049 8 MR 0815391 Chvatal Vaclav Sbihi Najiba 1987 Bull free Berge graphs are perfect Graphs and Combinatorics 3 2 127 139 doi 10 1007 BF01788536 MR 0932129 Cornuejols Gerard 2002 The strong perfect graph conjecture Proceedings of the International Congress of Mathematicians Vol III Beijing 2002 PDF Beijing Higher Ed Press pp 547 559 MR 1957560 Cornuejols G Cunningham W H 1985 Compositions for perfect graphs Discrete Mathematics 55 3 245 254 doi 10 1016 S0012 365X 85 80001 7 MR 0802663 Hougardy S 1991 Counterexamples to three conjectures concerning perfect graphs Technical Report RR870 M Grenoble France Laboratoire Artemis IMAG Universita Joseph Fourier As cited by Roussel Rusu amp Thuillier 2009 Konig Denes 1916 Grafok es alkalmazasuk a determinansok es a halmazok elmeletere Matematikai es Termeszettudomanyi Ertesito 34 104 119 Lovasz Laszlo 1972a Normal hypergraphs and the perfect graph conjecture Discrete Mathematics 2 3 253 267 doi 10 1016 0012 365X 72 90006 4 Lovasz Laszlo 1972b A characterization of perfect graphs Journal of Combinatorial Theory Series B 13 2 95 98 doi 10 1016 0095 8956 72 90045 7 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 Reed B A 1986 A semi strong perfect graph theorem Ph D thesis Montreal Quebec Canada Department of Computer Science McGill University As cited by Roussel Rusu amp Thuillier 2009 Roussel F Rusu I Thuillier H 2009 The strong perfect graph conjecture 40 years of attempts and its resolution Discrete Mathematics 309 20 6092 6113 doi 10 1016 j disc 2009 05 024 MR 2552645 Rusu Irena 1997 Building counterexamples Discrete Mathematics 171 1 3 213 227 doi 10 1016 S0012 365X 96 00081 7 MR 1454452 Seymour Paul 2006 How the proof of the strong perfect graph conjecture was found PDF Gazette des Mathematiciens 109 69 83 MR 2245898 External links EditThe Strong Perfect Graph Theorem Vaclav Chvatal Weisstein Eric W Strong Perfect Graph Theorem MathWorld Retrieved from https en wikipedia org w index php title Strong perfect graph theorem amp oldid 1097037132, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.