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:
“I remember a very important lesson that my father gave me when I was twelve or thirteen. He said, “You know, today I welded a perfect seam and I signed my name to it.” And I said, “But, Daddy, no one’s going to see it!” And he said, “Yeah, but I know it’s there.” So when I was working in kitchens, I did good work.”
—Toni Morrison (b. 1931)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)