Chapter 5: Coloring of Graphs

Source: Introduction to Graph Theory, 2nd Edition, by Douglas B. West

Overview

Chapter 5 of West's Introduction to Graph Theory (2nd Edition) covers the theory of graph coloring, one of the most fundamental topics in graph theory. The chapter spans pages 191–232 and is divided into three main sections: vertex colorings and their upper bounds, the structural properties of graphs requiring many colors, and the enumerative theory of colorings via the chromatic polynomial. The chapter builds from basic definitions through deep structural theorems (Brooks' Theorem, Turán's Theorem) to algebraic and enumerative tools (the chromatic polynomial, perfect graphs).

5.1 Vertex Colorings and Upper Bounds

Basic Definitions and Lower Bounds

Proper k-coloring: A labeling f: V(G) → {1, ..., k} such that adjacent vertices receive different colors (Definition 5.1.1–5.1.2).
Chromatic number χ(G): The minimum k such that G has a proper k-coloring. A graph is k-chromatic if χ(G) = k and k-colorable if χ(G) ≤ k.
k-critical graph: A k-chromatic graph such that every proper subgraph has chromatic number less than k. Equivalently, χ(G − e) < χ(G) for every edge e (Remark 5.2.12).
Proposition 5.1.7: For every graph G, χ(G) ≥ ω(G) (the clique number) and χ(G) ≥ n(G)/α(G) (the independence number bound). Both bounds are tight for complete graphs.
Example 5.1.8: χ(G) can exceed ω(G) arbitrarily. The join of C_2r+1 and K_s has ω(G) = s + 2 but χ(G) ≥ s + 3.

Chromatic Number and Graph Operations

For the disjoint union: χ(G + H) = max{χ(G), χ(H)}.
For the join: χ(G ∨ H) = χ(G) + χ(H).
Cartesian product (Definition 5.1.9): G □ H has vertex set V(G) × V(H), with (u, v) adjacent to (u', v') iff u = u' and vv' ∈ E(H), or v = v' and uu' ∈ E(G).
Proposition 5.1.11 (Vizing [1963], Aberth [1964]): χ(G □ H) = max{χ(G), χ(H)}.

Upper Bounds and Greedy Coloring

Greedy coloring (Algorithm 5.1.12): Color vertices in a fixed order, assigning each vertex the smallest color not used by its earlier neighbors.
Proposition 5.1.13: χ(G) ≤ Δ(G) + 1, since greedy coloring uses at most Δ(G) + 1 colors.
Proposition 5.1.14 (Welsh–Powell [1967]): With vertices ordered by nonincreasing degree d₁ ≥ ... ≥ d_n, χ(G) ≤ 1 + max_i min{d_i, i − 1}.

Interval Graphs

Example 5.1.15: Register allocation modeled as graph coloring. Variables are vertices; two are adjacent if their active intervals overlap. This defines an interval graph.
Proposition 5.1.16: For interval graphs, χ(G) = ω(G). Greedy coloring on the left-endpoint ordering is optimal.

Critical Subgraphs and the Szekeres–Wilf Bound

Lemma 5.1.18: If H is k-critical, then δ(H) ≥ k − 1.
Theorem 5.1.19 (Szekeres–Wilf [1968]): χ(G) ≤ 1 + max_{H ⊆ G} δ(H). This is called the degeneracy bound.

Gallai–Roy–Vitaver Theorem

Theorem 5.1.21 (Gallai [1968], Roy [1967], Vitaver [1962]): If D is an orientation of G with longest directed path length ℓ(D), then χ(G) ≤ 1 + ℓ(D). Furthermore, equality holds for some orientation.
This connects chromatic number to directed path lengths in orientations.

Brooks' Theorem

Theorem 5.1.22 (Brooks [1941]): If G is a connected graph that is not a complete graph or an odd cycle, then χ(G) ≤ Δ(G).
This is a major improvement over the Δ(G) + 1 bound, showing that equality in the greedy bound holds only for complete graphs and odd cycles.
Remark 5.1.23: The bound can be further improved when G has no large clique. Brooks' Theorem also implies the Petersen graph is 3-colorable.

Conjectures and Extensions

Reed [1998] conjectured χ(G) ≤ ⌈(Δ(G) + 1 + ω(G)) / 2⌉.
Borodin and Kostochka [1977] conjectured that ω(G) < Δ(G) implies χ(G) < Δ(G) when Δ(G) ≥ 9.

5.2 Structure of k-chromatic Graphs

Graphs with Large Chromatic Number

Mycielski's construction (Definition 5.2.1): From a simple graph G with vertices {v₁, ..., v_n}, construct G' by adding copies {u₁, ..., u_n} with u_i adjacent to N_G(v_i), plus a universal vertex w adjacent to all u_i.
Theorem 5.2.3 (Mycielski [1955]): From a k-chromatic triangle-free graph G, Mycielski's construction produces a (k+1)-chromatic triangle-free graph G'.
Remark 5.2.4: Starting from K₂, iterating Mycielski's construction yields a sequence of triangle-free graphs with arbitrarily large chromatic number. The first three are K₂, C₅, and the Grötzsch graph (the smallest 4-chromatic triangle-free graph). The order grows as n(G_k) = 3 · 2^k−2 − 1.
Erdős [1959] proved probabilistically that triangle-free k-chromatic graphs exist with at most c · k^2+ε vertices, and the true minimum f(k) satisfies c₁ · k² · log(k) ≤ f(k) ≤ c₂ · k² · log(k).

Extremal Problems and Turán's Theorem

Complete multipartite graph (Definition 5.2.6): A graph whose vertices can be partitioned into independent sets with complete adjacency between sets. Written K_{n₁, ..., n_k}.
Turán graph T_n,r (Example 5.2.7): The complete r-partite graph on n vertices with partite sets differing in size by at most 1.
Lemma 5.2.8: Among simple r-partite graphs with n vertices, the Turán graph has the most edges.
Theorem 5.2.9 (Turán [1941]): Among n-vertex simple graphs with no (r+1)-clique, T_n,r has the maximum number of edges. This foundational result is the origin of extremal graph theory.
Example 5.2.10–5.2.11: Geometric applications of Turán's theorem, including the "distant pairs of points" problem.

Color-Critical Graphs

Remark 5.2.12: A graph with no isolated vertices is color-critical iff χ(G − e) < χ(G) for every edge e.
Proposition 5.2.13: In a k-critical graph: (a) for every vertex v, some proper k-coloring uses v's color nowhere else and the other k−1 colors all appear on N(v); (b) for every edge e, every proper (k−1)-coloring of G − e assigns the same color to both endpoints of e.
Lemma 5.2.15 (Kainen): If χ(G) > k and G[X], G[Y] are both k-colorable for a partition {X, Y} of V(G), then the edge cut [X, Y] has at least k edges.
Theorem 5.2.16 (Dirac [1953]): Every k-critical graph is (k−1)-edge-connected.
S-lobe (Definition 5.2.17): For a vertex set S, an S-lobe is an induced subgraph consisting of S and the vertices of one component of G − S.
Proposition 5.2.18: If G is k-critical, then G has no cutset of pairwise adjacent vertices. In particular, if {x, y} is a cutset, then x is not adjacent to y, and G has an S-lobe H such that χ(H + xy) = k.

Forced Subdivisions

H-subdivision (Definition 5.2.19): A graph obtained from H by replacing edges with pairwise internally disjoint paths.
Theorem 5.2.20 (Dirac [1952a]): Every graph with chromatic number at least 4 contains a K₄-subdivision.
Remark 5.2.21: Hajós [1961] conjectured every k-chromatic graph contains a K_k-subdivision. This is true for k ≤ 4 and false for k ≥ 7 (Catlin [1979]).
Hadwiger's Conjecture (Hadwiger [1943]): Every k-chromatic graph has K_k as a minor (obtainable via edge contractions). This is equivalent to the Four Color Theorem for k = 5, and remains open for k ≥ 7.
Theorem 5.2.23 (Mader [1967], Thomassen [1988]): If F and G are simple graphs with e(F) = m, δ(F) ≥ 1, and δ(G) ≥ 2^m, then G contains a subdivision of F.
Lemma 5.2.22 (Mader [1967]): If G is a simple graph with minimum degree at least 2k, then G contains disjoint subgraphs G' (connected, δ(G') ≥ k) and H such that every vertex of G' has a neighbor in H.

5.3 Enumerative Aspects

Counting Proper Colorings

Definition 5.3.1: χ(G; k) is the number of proper colorings f: V(G) → [k]. This counts ordered colorings (i.e., which vertex gets which specific color).
Example 5.3.2: χ(K_n; k) = kⁿ (edgeless graph) and χ(K_n; k) = k(k−1)...(k−n+1) (complete graph).
Proposition 5.3.3: If T is a tree with n vertices, then χ(T; k) = k(k−1)ⁿ⁻¹.

The Chromatic Polynomial

Proposition 5.3.4: χ(G; k) is a polynomial in k of degree n(G), called the chromatic polynomial.
Example 5.3.5: Computation of χ(C₄; k) = k(k−1)(k² − 3k + 3) via partitions into independent sets.
Theorem 5.3.6 (Chromatic recurrence): For any edge e ∈ E(G), χ(G; k) = χ(G − e; k) − χ(G · e; k), where G − e is edge deletion and G · e is edge contraction.
Theorem 5.3.8 (Whitney [1933c]): The chromatic polynomial χ(G; k) has degree n(G), with integer coefficients alternating in sign, beginning 1, −e(G), ....
Example 5.3.9: Adding an edge yields a chromatic recurrence in the reverse direction: χ(G; k) = χ(G − e; k) + χ(G · e; k), useful for computing χ(K_n − e; k).
Theorem 5.3.10 (Whitney [1932b]): χ(G; k) = Σ_{S ⊆ E(G)} (−1)^|S| · k^c(G(S)), where c(G(S)) is the number of components of the spanning subgraph with edge set S. This is an inclusion-exclusion formula.

Chordal Graphs

Simplicial vertex: A vertex whose neighborhood induces a clique. A simplicial elimination ordering is a deletion ordering v_n, ..., v₁ such that each v_i is simplicial in the remaining graph (Definition 5.3.12).
Example 5.3.13: For a simplicial elimination ordering, the chromatic polynomial factors as a product of linear terms: χ(G; k) = Π (k − d(i)) where d(i) = |N(v_i) ∩ {v₁, ..., v_i−1}|.
Chord and chordal graph (Definition 5.3.15): A chord of a cycle C is an edge joining two non-consecutive vertices of C. A chordless cycle has length at least 4 with no chord. A graph is chordal if it has no chordless cycle.
Lemma 5.3.16 (Voloshin [1982], Farber–Jamison [1986]): In a chordal graph, a simplicial vertex exists farthest from any given vertex.
Theorem 5.3.17 (Dirac [1961]): A graph has a simplicial elimination ordering if and only if it is chordal. This is a TONCAS (The Only Necessary Condition is Also Sufficient) theorem.

A Hint of Perfect Graphs

Perfect graph (Definition 5.3.18): A graph G such that χ(H) = ω(H) for every induced subgraph H of G.
Clique cover number θ(G): The minimum number of cliques needed to cover V(G). Note θ(G) = χ(G).
Perfect Graph Theorem (Lovász [1972a, 1972b]): G is perfect if and only if its complement G is perfect.
Hereditary family (Definition 5.3.19): A family of graphs closed under taking induced subgraphs.
Example 5.3.21: Bipartite graphs and their line graphs are perfect. Interval graphs are perfect (since they are chordal).
Theorem 5.3.22 (Berge [1960]): Chordal graphs are perfect. Greedy coloring on the reverse of a simplicial elimination ordering produces an optimal coloring.
Comparability graphs (Definition 5.3.23): Graphs admitting a transitive orientation. Proposition 5.3.25 (Berge [1960]): Comparability graphs are perfect.

Counting Acyclic Orientations (optional)

Acyclic orientation: An orientation of G with no directed cycle. Setting k = −1 in χ(G; k) counts acyclic orientations.
Example 5.3.26: C₄ has 14 acyclic orientations, matching χ(C₄; k) evaluated at k = −1 (with appropriate sign).
Theorem 5.3.27 (Stanley [1973]): The value of χ(G; k) at k = −1 is (−1)^n(G) times the number of acyclic orientations of G.

Key Themes and Significance

The gap between ω(G) and χ(G): A central theme of the chapter. While χ(G) ≥ ω(G) always holds, the gap can be arbitrarily large (Mycielski's construction), yet structural conditions can force equality (perfect graphs, interval graphs, chordal graphs).

Greedy coloring and its refinements: The simple greedy algorithm yields χ(G) ≤ Δ(G) + 1. Brooks' Theorem sharpens this to χ(G) ≤ Δ(G) for all graphs except complete graphs and odd cycles, which is best possible.

Extremal graph theory: Turán's Theorem determines the maximum number of edges in a graph with no (r+1)-clique, establishing the Turán graph as the unique extremal graph. This foundational result launched the field of extremal graph theory.

Critical graphs and connectivity: k-critical graphs must be (k−1)-edge-connected (Dirac), and their structure is constrained in terms of cutsets and S-lobes.

The chromatic polynomial: The function χ(G; k) counting proper k-colorings is always a polynomial, computable via deletion-contraction recurrence or Whitney's inclusion-exclusion formula. Its properties (alternating coefficients, evaluation at k = −1 counting acyclic orientations) reveal deep connections between coloring and orientation.

Perfect graphs: The class of graphs where χ = ω for all induced subgraphs unifies interval graphs, chordal graphs, bipartite graphs, and comparability graphs. The Perfect Graph Theorem (Lovász) shows perfection is closed under complementation.

Flags

Introduction to Graph Theory/Coloring of Graphs

From charlesreid1

Contents