Perfect Graphs and Advanced Coloring

Perfect graphs form a rich class where the chromatic number equals the clique number for every induced subgraph. The Strong Perfect Graph Theorem, proved in 2006, gives a complete characterization.

Perfect Graphs

Definition5.6Perfect Graph

A graph $G$ is perfect if $\chi(H) = \omega(H)$ for every induced subgraph $H$ of $G$ . Equivalently (by the Perfect Graph Theorem of Lovász, 1972): $G$ is perfect if and only if its complement $\bar{G}$ is perfect. Examples: bipartite graphs, chordal graphs, comparability graphs, co-comparability graphs.

Definition5.7Strong Perfect Graph Theorem

A graph is perfect if and only if it contains no odd hole ( $C_{2k+1}$ with $k \geq 2$ ) and no odd antihole ( $\overline{C_{2k+1}}$ with $k \geq 2$ ) as an induced subgraph. This was conjectured by Berge (1961) and proved by Chudnovsky, Robertson, Seymour, and Thomas (2006). The proof is over 150 pages and uses a structural decomposition theory for Berge graphs.

Fractional and Circular Coloring

ExampleFractional Chromatic Number

The fractional chromatic number $\chi_f(G)$ is the linear programming relaxation of $\chi(G)$ : minimize $\sum_I x_I$ over independent sets $I$ subject to $\sum_{I \ni v} x_I \geq 1$ for all $v$ , $x_I \geq 0$ . Always $\omega(G) \leq \chi_f(G) \leq \chi(G)$ , and $\chi_f = \omega$ for perfect graphs. For the Kneser graph: $\chi_f(K(n,k)) = n/k$ , demonstrating that $\chi_f$ and $\chi$ can differ significantly.

RemarkCircular Chromatic Number

The circular chromatic number $\chi_c(G)$ generalizes $\chi(G)$ : it is the infimum of $p/q$ over integers $p \geq 2q$ such that $G$ has a $(p,q)$ -coloring (vertices get arcs of length $q$ on a circle of circumference $p$ , with adjacent arcs non-overlapping). Always $\chi(G) - 1 < \chi_c(G) \leq \chi(G)$ , and $\chi(G) = \lceil \chi_c(G) \rceil$ . The circular chromatic number provides a finer measure of colorability.

Coloring Sparse Graphs

Definition5.8Coloring Planar and Sparse Graphs

The Four Color Theorem: every planar graph is 4-colorable. The Five Color Theorem (simpler proof): every planar graph is 5-colorable (by induction using Euler's formula: $\delta(G) \leq 5$ ). For graphs on surfaces: the Heawood bound $\chi \leq \lfloor(7 + \sqrt{1 + 48g})/2\rfloor$ for genus $g \geq 1$ is tight for all $g \geq 1$ (Ringel-Youngs theorem). Graphs with large girth have small chromatic number: $\chi(G) = O(\Delta/\log\Delta)$ for triangle-free graphs (Johansson, 1996).

ExampleThomassen's Five-Choosability Theorem

Thomassen (1994) proved every planar graph is 5-choosable (list chromatic number $\leq 5$ ) with an elegant inductive proof. Whether every planar graph is 4-choosable is false: Voigt (1993) constructed a planar graph that is not 4-choosable. This shows list coloring is strictly harder than ordinary coloring for planar graphs.