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 ).

See also Perfect Graph
Explore with Wolfram|Alpha
References Godsil, C. and Royle, G. "Imperfect Graphs." §7.6 in Algebraic
Graph Theory. New York: Springer-Verlag, pp. 142-145, 2001. Sloane,
N. J. A. Sequences A187236 and A187237 in "The On-Line Encyclopedia of Integer
Sequences." West, D. B. "Imperfect Graphs." Introduction
to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 334-340,
2000. Referenced on Wolfram|Alpha Imperfect Graph
Cite this as:
Weisstein, Eric W. "Imperfect Graph."
From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/ImperfectGraph.html

Subject classifications