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.

REFERENCES

Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.

Bohman, T. and Holzman, R. "A Nontrivial Lower Bound on the Shannon Capacities of the Complements of Odd Cycles." IEEE Trans. Inform. Th. 49, 721-722, 2003.

Chudnovsky, M.; Cornuéjols, G.; Liu, X.; Seymour, P.; and Vušković, K. "Recognizing Berge Graphs." Combinatorica 25, 143-186, 2005.

Godsil, C. and Royle, G. Algebraic Graph Theory. New York: Springer-Verlag, pp. 142-143, 2001.

Golumbic, M. C. Algorithmic Graph Theory and Perfect Graphs. New York: Academic Press, 1980.

Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, 2006.

Ravindra, G. "Some Classes of Strongly Perfect Graphs." Disc. Math. 206, 197-203, 1999.

Skiena, S. "Perfect Graphs." §5.6.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 219, 1990.

Sloane, N. J. A. Sequences A052431 and A052433 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "A Hint of Perfect Graphs" and "Perfect Graphs." §8.1 in Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 226-228 and 319-348, 2000.