Perfect Graph

A perfect graph is a graph such that for every induced subgraph of , the clique number equals the chromatic number, i.e., . A graph that is not a perfect graph is called an imperfect graph (Godsil and Royle 2001, p. 142).

A graph for which (without any requirement that this condition also hold on induced subgraphs) is called a weakly perfect graph. All perfect graphs are therefore weakly perfect by definition.

A graph is strongly perfect if every induced subgraph has an independent set meeting all maximal cliques of . While all strongly perfect graphs are perfect, the converse is not necessarily true. Since every -free graph (where is a path graph) is strongly perfect (Ravindra 1999) and every strongly perfect graph is perfect, if a graph is -free, it is perfect.

Perfect graphs were introduced by Berge (1973) motivated in part by determining the Shannon capacity of graphs (Bohman 2003). Note that rather confusingly, perfect graphs are distinct from the class of graphs with perfect matchings.

Every bipartite graph is perfect (Gross and Yellen 2006, p. 385). The perfect graph theorem states that the graph complement of a perfect graph is itself perfect. A graph is therefore perfect iff its complement is perfect. However, determining if a general graph is perfect has been shown to be a polynomial time algorithm (Chudnovsky et al. 2005).

A graph is perfect iff neither the graph nor its graph complement has a chordless cycle of odd order. A graph with no 5-cycle and no larger odd chordless cycle is therefore automatically perfect. This is true since the presence of a chordless 5-cycle in corresponds to a 5-cycle in and can have no chordless 7-cycle or larger since the diagonals of these cycles in would contain a 5-cycle in .

A graph can be tested to see if it is perfect using PerfectQ[g] in the Wolfram Language package Combinatorica` .

The numbers of perfect graphs on , 2, ... nodes are 1, 2, 4, 11, 33, 148, 906, 8887, ... (OEIS A052431).

The numbers of perfect connected graphs on , 2, ... nodes are 1, 1, 2, 6, 20, 105, 724, ... (OEIS A052433).

Classes of graphs that are perfect include:

1. bipartite graphs

2. chordal graphs

3. line graphs of bipartite graphs,

4. graph complements of bipartite graphs

5. graph complements of line graphs of bipartite graphs.

Families of perfect graphs (excluding bipartite families) include

1. barbell graphs

2. bishop graphs

3. caveman graphs

4. complete graphs

5. empty graphs

6. fan graphs

7. Hanoi graphs

8. helm graphs for or even

9. rook graphs

10. lollipop graphs

11. king graphs with

12. queen graphs , and

13. sun graphs

14. Turán graphs

15. triangular snake graphs

16. windmill graphs.

Wolfram Web Resources