Combinatorics and Graph Theory · Problem 5.8.5

Graph Theory — David Guichard

Mathematics — Combinatorics · graph-coloring

Problem

Prove theorem 5.8.12 as follows. By corollary 5.8.11 we need consider only regular graphs. Regular graphs of degree 2 are easy, so we consider only regular graphs of degree at least 3. If GG is not 2-connected, show that the blocks of GG may be colored with Δ(G)\Delta(G) colors, and then the colorings may be altered slightly so that they combine to give a proper coloring of GG. If GG is 2-connected, show that there are vertices u,v,wu, v, w such that uu is adjacent to both vv and ww, vv and ww are not adjacent, and G−v−wG - v - w is connected. Given such vertices, color vv and ww with color 1, then color the remaining vertices by a greedy algorithm similar to that in theorem 5.8.10, with uu playing the role of vnv_n. To show the existence of u,v,wu, v, w as required, let xx be a vertex not adjacent to all other vertices. If G−xG - x is 2-connected, let v=xv = x, let ww be at distance 2 from vv (justify this), and let a path of length 2 be v,u,wv, u, w. Use theorem 5.7.4 to show that u,v,wu, v, w have the required properties. If G−xG - x is not 2-connected, let u=xu = x and let vv and ww be (carefully chosen) vertices in two different endblocks of G−xG - x. Show that u,v,wu, v, w have the required properties.
Intuitive explanation

The key insight is that edge-coloring regular graphs reduces to vertex-coloring via a clever decomposition: color blocks independently (or handle the 2-connected case specially), then exploit the structure of vertices and their neighborhoods to ensure colors combine properly. For 2-connected graphs, finding vertices u,v,wu, v, w where vv and ww are non-adjacent but both neighbor uu lets you "pair them up" with one color, then greedily color the rest while keeping uu last—this guarantees uu has a free color because its neighbors use at most Δ(G)−1\Delta(G) - 1 colors total.

Intuitive explanation

The key insight is that edge-coloring regular graphs reduces to vertex-coloring via a clever decomposition: color blocks independently (or handle the 2-connected case specially), then exploit the structure of vertices and their neighborhoods to ensure colors combine properly. For 2-connected graphs, finding vertices u,v,wu, v, w where vv and ww are non-adjacent but both neighbor uu lets you "pair them up" with one color, then greedily color the rest while keeping uu last—this guarantees uu has a free color because its neighbors use at most Δ(G)−1\Delta(G) - 1 colors total.

Related theory

Browse the problem library