Perfect graphs

doi:10.1017/CBO9781139519793.010

7 - Perfect graphs

Published online by Cambridge University Press: 05 May 2015

Nicolas Trotignon

Edited by

Lowell W. Beineke and

Robin J. Wilson

Show author details

Nicolas Trotignon: Affiliation:
University Paris Diderot
Lowell W. Beineke: Affiliation:
Purdue University, Indiana
Robin J. Wilson: Affiliation:
The Open University, Milton Keynes

Book contents

Get access

Summary

Perfect graphs were defined by Claude Berge in the 1960s. They are important objects for graph theory, linear programming and combinatorial optimization. Berge made a conjecture about them (now called the strong perfect graph theorem or SPGT) which was proved by Chudnovsky, Robertson, Seymour and Thomas in 2002. This survey about perfect graphs mostly focuses on the SPGT.

Introduction

Every graph G clearly satisfies χ(G) ≥ ω(G), where ω(G) is the clique number of G, because the vertices of a clique must receive different colours. A graph G is perfect if every induced subgraph H of G satisfies χ(H) = ω(H). A chordless cycle of length 2k + 1, for k ≥ 2, satisfies 3 = χ > ω = 2, and its complement satisfies k + 1 = χ > ω = k; these graphs are therefore imperfect. Since perfect graphs are closed under taking induced subgraphs, they must be defined by excluding a family F of graphs as induced subgraphs. The strong perfect graph theorem (SPGT for short) states that the two examples just given are the only members of F.

Let us make this more formal. A hole in a graph G is an induced cycle of length at least 4, and an antihole is a hole of G. A graph is Berge if it does not contain an odd hole or an odd antihole. The following was conjectured by Berge [3] in the 1960s and was the object of much research until it was finally proved in 2002 by Chudnovsky, Robertson, Seymour and Thomas [13].

Theorem 1.1 (Strong perfect graph theorem) A graph is perfect if and only if it is Berge.

One direction of the proof is easy: every perfect graph is Berge since, as we observed above, odd holes and antiholes satisfy χ = ω + 1. The proof of the converse statement is very long and relies on structural graph theory.

Type: Chapter
Information: Topics in Chromatic Graph Theory , pp. 137 - 160

DOI: https://doi.org/10.1017/CBO9781139519793.010 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2015

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. N., Alexeev, A., Fradkin and I., Kim, Forbidden induced subgraphs of double-split graphs, SIAMJ. Discrete Math. 26 (2012), 1–14.Google Scholar

2. L. W., Beineke, Characterizations of derived graphs, J. Combin. Theory 9 (1970), 129–135.Google Scholar

3. C., Berge, Färbung von, Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind, Technical report, Wiss. Z. der Martin-Luther-Univ. Halle-Wittenberg, Math.–Natur. Reihe 10, 1961.

4. C., Berge and V., Chvatal (eds.), Topics on Perfect Graphs, Ann. Discrete Math. 21, North-Holland, 1984.

5. J. A., Bondy and U. S. R., Murty, Graph Theory, Graduate Texts in Math. 244, Springer, 2008.Google Scholar

6. A., Brandstadt, V. B., Le and J. P., Spinrad, Graph Classes: A Survey, SIAM, 1999.Google Scholar

7. M., Burlet, F., Maffray and N., Trotignon, Odd pairs of cliques, Graph Theory in Paris, Proc. Conf. in Memory of Claude Berge (eds. A., Bondy et al.), BirkMuser (2007), 85–95.Google Scholar

8. P., Charbit, M., Habib, N., Trotignon and K., Vuskovic, Detecting 2-joins faster, J. Discrete Algorithms 17 (2012), 60–66.Google Scholar

9. M., Chudnovsky, Berge Trigraphs and their Applications, Ph.D. thesis, Princeton University, 2003.Google Scholar

10. M., Chudnovsky, Berge, trigraphs, J. Graph Theory 53 (2006), 1–55.

11. M., Chudnovsky, G., Cornuejols, X., Liu, P., Seymour and K., Vuskovic, Recognizing Berge graphs, Combinatorica 25 (2005), 143–186.Google Scholar

12. M., Chudnovsky, N., Robertson, P., Seymour and R., Thomas, Progress on perfect graphs, Math. Programming (B) 97 (2003), 405–422.Google Scholar

13. M., Chudnovsky, N., Robertson, P., Seymour and R., Thomas, The strong perfect graph theorem, Ann. of Math. 164 (2006), 51–229.Google Scholar

14. M., Chudnovsky and P., Seymour, Excluding induced subgraphs, Surveys in Combinatorics, 2007, London Math. Soc. Lecture Notes 346 (2007), 99–119.Google Scholar

15. M., Chudnovsky and P., Seymour, Even pairs in Berge graphs, J. Combin. Theory (B) 99 (2009), 370–377.Google Scholar

16. M., Chudnovsky and P., Seymour, Three-colourable perfect graphs without even pairs, J. Combin. Theory (B) 102 (2012), 363–394.Google Scholar

17. M., Chudnovsky, N., Trotignon, T., Trunck and K., Vuskovic, Coloring perfect graphs with no balanced skew-partitions, submitted.

18. V., Chvátal, On certain polytopes associated with graphs, J. Combin. Theory (B) 18 (1975), 138–154.Google Scholar

19. V., Chvátal, Star-cutsets and perfect graphs, J. Combin. Theory (B) 39 (1985), 189–199.Google Scholar

20. V., Chvátal and N., Sbihi, Bull-free Berge graphs are perfect, Graphs Combin. 3 (1987), 127–139.Google Scholar

21. M., Conforti, G., Cornuejols, X., Liu, K., Vuskovic and G., Zambelli, Odd hole recognition in graphs of bounded clique size, SIAM J. Discrete Math. 20 (2006), 42–48.Google Scholar

22. M., Conforti, G., Cornuejols and K., Vušković, Square-free perfect graphs, J. Combin. Theory (B) 90 (2004), 257–307.Google Scholar

23. M., Conforti, G., Cornuejols and K., Vuskovic, Decomposition of odd-hole-free graphs by double star cutsets and 2-joins, Discrete Appl. Math. 141 (2004), 41–91.Google Scholar

24. M., Conforti and M. R., Rao, Testing balancedness and perfection of linear matrices, Math. Programming 61 (1993), 1–18.Google Scholar

25. G., Cornuéjols, Combinatorial Optimization: Packing and Covering, CBMS-NSF Regional Conf. Series in Applied Math. 74, SIAM, 2001.Google Scholar

26. G., Cornuéjols and W. H., Cunningham, Composition for perfect graphs, Discrete Math. 55 (1985), 245–254.Google Scholar

27. E., Diot, S., Tavenas and N., Trotignon, Detecting wheels, Analysis Discrete Math. 8 (2014), 111–122.Google Scholar

28. Y., Faenza, G., Oriolo and G., Stauffer, An algorithmic decomposition of claw-free graphs leading to an O(n3)-algorithm for the weighted stable set problem, SODA (2011), 630–646.

29. J., Fonlupt and J. P., Uhry, Transformations which preserve perfectness and h-perfectness of graphs, Bonn Workshop on Combinatorial Optimization (eds. A., Bachem, M., Grötschel and B., Korte), Ann. Discrete Math. 16 (1982), 83–85.Google Scholar

30. D. R., Fulkerson, Anti-blocking polyhedra, J. Combin. Theory (B) 12 (1972), 50–71.Google Scholar

31. T., Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66.Google Scholar

32. G. S., Gasparian, Minimal imperfect graphs: a simple approach, Combinatorica 16 (1996), 209–212.Google Scholar

33. M. C., Golumbic, Algorithmic Graph Theory and Perfect Graphs, Elsevier, 2004.Google Scholar

34. M., Gröstchel, L., Lovász and A., Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.Google Scholar

35. A., Gyárfás, Problems from the world surrounding perfect graphs, Zastowania Mat. Appl. Math. 19 (1987), 413–441.Google Scholar

36. A., Gyárfás, Z., Li, R. C. S., Machado, A., Sebő, S., Thomassé and N., Trotignon, Complements of nearly perfect graphs, J. Combin. 4 (2013), 299–310.Google Scholar

37. M., Habib, A., Mamcarz and F., de Montgolfier, Algorithms for some H-join decompositions, LATIN 2012, 446–457.

38. S., Hougardy, Classes of perfect graphs, Discrete Math. 306 (2006), 2529–2571.Google Scholar

39. W. S., Kennedy and B., Reed, Fast Skew Partition Recognition, Lecture Notes in Computer Science 4535 (2008), 101–107.Google Scholar

40. P. G. H., Lehot, An optimal algorithm to detect a line graph and output its root graph, J. Assoc. Comp. Mach. 21 (1974), 569–575.Google Scholar

41. B., Lévêque and D., de Werra, Graph transformations preserving the stability number, Discrete Appl. Math. 160 (2012), 2752–2759.Google Scholar

42. B., Lévêque, F., Maffray, B., Reed and N., Trotignon, Coloring Artemis graphs, Theor. Comp. Sci. 410 (2009), 2234–2240.Google Scholar

43. L., Lovász, A characterization of perfect graphs, J. Combin. Theory (B) 13 (1972), 95–98.Google Scholar

44. L., Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972), 253–267.Google Scholar

45. L., Lovász, Perfect graphs, Selected Topics in Graph Theory (eds. L. W., Beineke and R. J., Wilson), Academic Press (1983), 55–87.Google Scholar

46. F., Maffray, Fast recognition of doubled graphs, Technical Report, Les Cahiers Leibniz 202, 2013.

47. F., Maffray and N., Trotignon, Algorithms for perfectly contractile graphs, SIAM J. Discrete Math. 19 (2005), 553–574.Google Scholar

48. F., Maffray and N., Trotignon, A class of perfectly contractile graphs, J. Combin. Theory (B) 96 (2006), 1–19.Google Scholar

49. H., Meyniel, A new property of critical imperfect graphs and some consequences, Europ. J. Combin. 8 (1987), 313–316.Google Scholar

50. J. L. Ramírez, Alfonsín and B. A., Reed (eds.), Perfect Graphs, Wiley Interscience, 2001.

51. B. A., Reed, Skew partitions in perfect graphs, Discrete Appl. Math. 156 (2008), 1150–1156.Google Scholar

52. F., Roussel and P., Rubio, About skew partitions in minimal imperfect graphs, J. Combin. Theory (B) 83 (2001), 171–190.Google Scholar

53. F., Roussel, I., Rusu and H., Thuillier, The Strong Perfect Graph Conjecture: 40 years of attempts and its resolution, Discrete Math. 309 (2009), 6092–6113.Google Scholar

54. N. D., Roussopoulos, A max {m, n} algorithm for determining the graph H from its line graph G, Inform. Proc. Letters 2 (1973), 108–112.Google Scholar

55. A., Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Springer, 2003.Google Scholar

56. P., Seymour, How the proof of the strong perfect graph conjecture was found, Gazette des Math. 109 (2006), 69–83.Google Scholar

57. N., Trotignon, Decomposing Berge graphs and detecting balanced skew partitions, J. Combin. Theory (B) 98 (2008), 173–225.Google Scholar

58. N., Trotignon and K., Vušković, On Roussel–Rubio–type lemmas and their consequences, Discrete Math. 311 (2011), 684–687.Google Scholar

59. N., Trotignon and K., Vuskovic, Combinatorial optimization with 2-joins, J. Combin. Theory (B) 102 (2012), 153–185.Google Scholar

60. K., Vušković, The world of hereditary graph classes viewed through Truemper configurations, Surveys in Combinatorics 2013, London Math. Soc. Lecture Notes 409 (2013), 265–326.Google Scholar

Book contents

7 - Perfect graphs

Summary

Access options

References

Save book to Kindle

Save book to Dropbox

Save book to Google Drive