Characterizations and The Perfect Graph Theorems
In his initial work on perfect graphs, Berge made two important conjectures on their structure that were only proved later.
The first of these two theorems was the perfect graph theorem of Lovász (1972), stating that a graph is perfect if and only if its complement is perfect. Thus, perfection (defined as the equality of maximum clique size and chromatic number in every induced subgraph) is equivalent to the equality of maximum independent set size and clique cover number.
The second theorem, conjectured by Berge, provided a forbidden graph characterization of the perfect graphs. An induced cycle of odd length at least 5 is called an odd hole. An induced subgraph that is the complement of an odd hole is called an odd antihole. An odd cycle cannot be perfect, because its chromatic number is three and its clique number is two. Similarly, the complement of an odd cycle of length 2k + 1 cannot be perfect, because its chromatic number is k + 1 and its clique number is k. (Alternatively, the imperfection of this graph follows from the perfect graph theorem and the imperfection of the complementary odd cycle). Because these graphs are not perfect, every perfect graph must be a Berge graph, a graph with no odd holes and no odd antiholes. Berge conjectured the converse, that every Berge graph is perfect. This was finally proven as the strong perfect graph theorem of Chudnovsky, Robertson, Seymour, and Thomas (2006).
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.
Read more about this topic: Perfect Graph
Famous quotes containing the words perfect and/or graph:
“Talk to every woman as if you loved her, and to every man as if he bored you, and at the end of your first season you will have the reputation of possessing the most perfect social tact.”
—Oscar Wilde (1854–1900)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)