An imperfect graph is a graph that is not perfect. Therefore, graphs with
(1)
|
where is the clique number and is the chromatic number are imperfect. A weaker form using a bound of states that a graph with
(2)
|
where is the independence number is imperfect.
By the perfect graph theorem, applying the above to the graph complement gives that a graph with
(3)
|
where is the clique covering number is also imperfect.
A graph is also imperfect iff either the graph or its complement has a chordless cycle of odd order.
Families of imperfect graphs include:
1. cycle graphs
2. fullerenes (which by definition contain an odd 5-cycle)
3. king graphs with
4. helm graphs for odd
5. wheel graphs
A list of imperfect graphs on small numbers of vertices is implemented in the Wolfram Language as GraphData["Imperfect"].
The numbers of simple imperfect graphs on , 2, ... vertices are 0, 0, 0, 0, 1, 8, 138, 3459, ... (OEIS A187236).
The numbers of connected imperfect graphs on , 2, ... vertices are 0, 0, 0, 0, 1, 7, 129, 3312,... (OEIS A187237).