Skip to main content Accessibility help
×
Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T03:39:34.253Z Has data issue: false hasContentIssue false

7 - Perfect graphs

Published online by Cambridge University Press:  05 May 2015

Nicolas Trotignon
Affiliation:
University Paris Diderot
Lowell W. Beineke
Affiliation:
Purdue University, Indiana
Robin J. Wilson
Affiliation:
The Open University, Milton Keynes
HTML view is not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Save book to Kindle

To save this book to your Kindle, first ensure no-reply@cambridge.org is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×