A perfect graph is a finite simple 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.
Berge (1973) studied perfect graphs, motivated in part by determining the Shannon capacity of graphs (Bohman and Holzman 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. Determining whether a general graph is perfect can be done by a polynomial time algorithm (Chudnovsky et al. 2005).
The strong perfect graph theorem states that a graph 
is perfect iff neither 
nor its graph complement 
has an odd
chordless cycle (Chudnovsky et al. 2006). 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 
.
The numbers of unlabeled perfect graphs on 
, 2, ... nodes are 1, 2,
4, 11, 33, 148, 906, 8887, ... (OEIS A052431).
The numbers of unlabeled 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 (by König's line coloring theorem),
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.
