Chapter 72. Perfect Graphs

A graph is perfect when its coloring behavior is completely controlled by its clique structure.

For a general graph, the clique number gives only a lower bound for the chromatic number:

where:

• $\chi(G)$ is the chromatic number,
• $\omega(G)$ is the size of a largest clique.

In many graphs, the chromatic number can be much larger than the clique number. Perfect graphs are exactly the graphs where this gap never appears, not only in the graph itself, but in every induced subgraph.

Perfect graphs form one of the central structural classes of graph theory. They connect coloring, optimization, matrix theory, combinatorics, and algorithms.

72.1 Definition

A graph $G$ is perfect if every induced subgraph $H$ satisfies

\chi(H)=\omega(H)

where:

• $\chi(H)$ is the chromatic number of $H$,
• $\omega(H)$ is the clique number of $H$.

This definition is standard in graph theory. (en.wikipedia.org)

The condition applies to every induced subgraph, not merely to $G$ itself.

This induced-subgraph condition is essential. A graph may satisfy

while still containing induced subgraphs where equality fails.

Perfectness is hereditary with respect to induced subgraphs.

72.2 Why Induced Subgraphs Matter

Suppose only the original graph were required to satisfy

This would be too weak.

For example, some graphs can have:

yet contain induced subgraphs with:

Such graphs behave imperfectly internally.

Perfect graph theory studies graphs where clique structure governs coloring at every scale.

This local-to-global consistency gives perfect graphs unusually strong structural properties.

72.3 First Examples

Complete Graphs

For the complete graph $K_n$,

and

Every induced subgraph of a complete graph is again complete.

Therefore complete graphs are perfect.

Bipartite Graphs

A bipartite graph satisfies:

If the graph has at least one edge, then:

Every induced subgraph of a bipartite graph is again bipartite.

Thus every induced subgraph satisfies:

Therefore bipartite graphs are perfect.

Trees

A tree is bipartite, hence perfect.

If the tree has at least one edge:

If the tree has one vertex:

72.4 Odd Cycles

Odd cycles provide the basic obstruction to perfectness.

Consider the cycle:

The largest clique has size 2:

However:

Thus:

Therefore $C_5$ is not perfect.

More generally, every odd cycle of length at least five is imperfect.

These cycles are called odd holes.

72.5 Complements of Odd Cycles

The complement graph of $G$, denoted $\overline{G}$, has the same vertex set as $G$, but edges are replaced by nonedges.

Odd cycle complements are also fundamental obstructions.

For example, the complement of $C_5$ is again $C_5$, so it is imperfect.

Odd complements of longer odd cycles are also imperfect.

These graphs are called odd antiholes.

Perfect graph theory is largely built around excluding odd holes and odd antiholes.

72.6 The Weak Perfect Graph Theorem

One of the first major results in the subject is the Weak Perfect Graph Theorem.

A graph is perfect if and only if its complement is perfect.

G\text{ perfect }\Longleftrightarrow \overline{G}\text{ perfect}

This theorem was proved by László Lovász.

The result is remarkable because coloring and clique structure interchange under complementation.

For any graph $G$:

The theorem shows that perfectness is symmetric under complementation.

72.7 Strong Perfect Graph Theorem

The central theorem of perfect graph theory is the Strong Perfect Graph Theorem.

A graph is perfect if and only if it contains:

• no odd hole,
• no odd antihole.

G\text{ perfect }\Longleftrightarrow G\text{ has no odd holes and no odd antiholes}

This theorem was conjectured for decades and finally proved by:

• Maria Chudnovsky,
• Neil Robertson,
• Paul Seymour,
• Robin Thomas.

The theorem gives a complete forbidden-subgraph characterization of perfect graphs. (en.wikipedia.org)

This is one of the deepest classification theorems in graph theory.

72.8 Chordal Graphs

A graph is chordal if every cycle of length at least four has a chord.

A chord is an edge joining two nonconsecutive vertices of the cycle.

Chordal graphs are perfect.

The reason is structural. Chordal graphs always contain simplicial vertices: vertices whose neighbors form a clique.

This allows recursive elimination and optimal coloring.

Chordal graphs are important because many hard graph problems become tractable on them.

72.9 Interval Graphs

An interval graph is formed from intervals on the real line.

Each interval becomes a vertex. Two vertices are adjacent when the intervals intersect.

Interval graphs are chordal, hence perfect.

In interval graphs:

• cliques correspond to overlapping interval families,
• coloring corresponds to assigning layers to intervals.

Interval graph coloring has efficient algorithms based on sorting interval endpoints.

These graphs appear in scheduling, genetics, memory allocation, and resource management.

72.10 Comparability Graphs

A comparability graph arises from a partially ordered set.

Vertices correspond to elements of the poset. Two vertices are adjacent when the corresponding elements are comparable.

Comparability graphs are perfect.

Their complements, called cocomparability graphs, are also perfect by the Weak Perfect Graph Theorem.

Perfect graph theory therefore includes many graphs arising naturally from order theory.

72.11 Coloring Perfect Graphs

For general graphs, computing chromatic number is NP-hard.

Perfect graphs behave differently.

For perfect graphs:

• chromatic number can be computed efficiently,
• optimal colorings can be found efficiently,
• maximum cliques can be found efficiently.

This algorithmic tractability is one reason perfect graphs are so important.

Optimization problems that are difficult in arbitrary graphs often become polynomial-time solvable in perfect graphs.

72.12 Clique Number and Chromatic Number

Perfect graphs are precisely the graphs where clique structure completely determines coloring complexity.

In arbitrary graphs:

may be strict.

In perfect graphs:

for every induced subgraph $H$.

Thus coloring reduces to clique computation.

This is highly unusual because clique problems are themselves generally difficult.

Perfect graphs create a rare setting where two difficult problems coincide exactly.

72.13 Stable Sets and Duality

Perfect graph theory has a strong dual nature.

Under graph complementation:

This symmetry explains why complements play such a central role.

Many perfect graph proofs come in dual pairs obtained through complementation.

72.14 Minimally Imperfect Graphs

A graph is minimally imperfect if:

• it is imperfect,
• every proper induced subgraph is perfect.

Odd holes and odd antiholes are minimally imperfect.

The Strong Perfect Graph Theorem states that these are the only minimally imperfect graphs.

Thus all imperfectness ultimately comes from odd holes and odd antiholes.

This gives perfect graph theory a remarkably clean obstruction structure.

72.15 Perfect Graph Classes

Many important graph families are perfect.

These classes arise naturally across combinatorics and applications.

Perfect graphs therefore unify many previously unrelated graph families.

72.16 Applications

Perfect graphs appear in optimization and scheduling.

Typical applications include:

In perfect graphs, optimal solutions often reduce to clique computations and linear programming methods.

This makes perfect graph theory important in combinatorial optimization.

72.17 Polyhedral Connections

Perfect graph theory is deeply connected with polyhedral combinatorics.

Stable-set polytopes of perfect graphs have especially clean descriptions.

Many optimization problems on perfect graphs can therefore be solved using linear programming rather than integer programming.

This connection helped establish perfect graphs as a central topic in modern combinatorics.

72.18 Recognition Problems

Determining whether a graph is perfect is nontrivial.

The Strong Perfect Graph Theorem provides a structural characterization, but recognizing odd holes and odd antiholes efficiently requires sophisticated algorithms.

Polynomial-time recognition algorithms exist, though they are considerably more complex than elementary graph algorithms.

Recognition theory is one of the major algorithmic branches of perfect graph theory.

72.19 Summary

Perfect graphs are graphs whose coloring behavior is completely determined by clique structure.

Their defining property is:

\chi(H)=\omega(H)\text{ for every induced subgraph }H

The main ideas are:

Perfect graph theory combines coloring, structure, optimization, and algorithms into one unified framework. It is one of the deepest and most influential areas of modern graph theory.

72.20 Exercises

1. Prove that complete graphs are perfect.

2. Prove that bipartite graphs are perfect.

3. Show that $C_5$ is not perfect.

4. Compute $\chi(C_5)$ and $\omega(C_5)$.

5. Explain why every tree is perfect.

6. Prove that every induced subgraph of a bipartite graph is bipartite.

7. Describe the complement of $C_5$.

8. Give an example of an odd hole.

9. Define an odd antihole.

10. Explain why perfectness must involve induced subgraphs.

11. Show that interval graphs are chordal.

12. Explain why chordal graphs are perfect.

13. Compare perfect graphs with arbitrary graphs.

14. Explain the relationship between cliques and coloring in perfect graphs.

15. State the Strong Perfect Graph Theorem.