Characterizations and the perfect graph theorems Perfect graph

a seven-vertex cycle , complement, showing in each case optimal coloring , maximum clique (shown heavy edges). since neither graph uses number of colors equal clique size, neither perfect.

the second theorem, conjectured berge, provided forbidden graph characterization of perfect graphs. induced cycle of odd length @ least 5 called odd hole. induced subgraph complement of odd hole called odd antihole. odd cycle of length greater 3 cannot perfect, because chromatic number 3 , clique number two. similarly, complement of odd cycle of length 2k + 1 cannot perfect, because chromatic number k + 1 , clique number k. (alternatively, imperfection of graph follows perfect graph theorem , imperfection of complementary odd cycle). because these graphs not perfect, every perfect graph must berge graph, graph no odd holes , no odd antiholes. berge conjectured converse, every berge graph perfect. proven strong perfect graph theorem of chudnovsky, robertson, seymour, , thomas (2006). trivially implies perfect graph theorem, hence name.

the perfect graph theorem has short proof, proof of strong perfect graph theorem long , technical, based on deep structural decomposition of berge graphs. related decomposition techniques have borne fruit in study of other graph classes, , in particular claw-free graphs.

there third theorem, again due lovász, suggested hajnal. states graph perfect if sizes of largest clique, , largest independent set, when multiplied together, equal or exceed number of vertices of graph, , same true induced subgraph. easy consequence of strong perfect graph theorem, while perfect graph theorem easy consequence of it.

the hajnal characterisation not met odd n-cycles or complements n >3: odd cycle on n >3 vertices has clique number 2 , independence number (n-1)/2. reverse true complement, in both cases product n-1.