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.
