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 an odd
chordless cycle. 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. block graphs,
3. chordal graphs,
4. distance-hereditary graphs,
5. line graphs of bipartite graphs,
6. Meyniel graphs,
7. trees,
8. graph complements of bipartite graphs, and
9. 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. 
-double cone graphs for 
or 
even,
6. empty graphs 
,
7. fan graphs,
8. Hanoi graphs,
9. helm graphs 
for 
or 
even,
10. rook graphs,
11. lollipop graphs,
12. king graphs 
with 
,
13. Ptolemaic graphs,
14. queen graphs 
, 
and 
,
15. sun graphs,
16. Turán graphs,
17. triangular snake graphs 
, and
18. windmill graphs.
