Ch.5: Colorings of Graphs

From the lecture notes "Combinatorics, Graphs, Matroids" (University of Bonn, winter term 2025/26) 5.1. Vertex Colorings 5.2. List-Colorings 5.3. Edge Colorings

120 flashcards · Mathematics · by lakesare

Part of University of Bonn › V3C2: Combinatorics, Graphs, Matroids · 6 courses

1. [Colorings of Graphs] In the chapter on colorings of graphs, which graphs are considered?

   Simple undirected graphs (no loops, no parallel edges). A loop {v,v}\{v, v\}{v,v} would demand c(v)≠c(v)c(v) \ne c(v)c(v)=c(v) , so no graph with a loop has a vertex coloring.

2. [Vertex Colorings] What is a vertex coloring of a graph GGG ?

   A map c:V(G)→N∖{0}c : V(G) \to \mathbb{N} \setminus \{0\}c:V(G)→N∖{0} with c(v)≠c(w)c(v) \ne c(w)c(v)=c(w) for every edge {v,w}\{v, w\}{v,w} . Adjacent vertices get different colors.

3. [Vertex Colorings] When is a vertex coloring ccc of GGG a kkk -vertex coloring, and when is GGG kkk -colorable?

   kkk -vertex coloring: c(v)≤kc(v) \le kc(v)≤k for all vvv . kkk -colorable: GGG has a kkk -vertex coloring. So a kkk -vertex coloring uses only the colors 1,…,k1, \dots, k1,…,k .

4. [Vertex Colorings] What are the color classes of a kkk -vertex coloring ccc of GGG ?

   The sets {v∈V(G)∣c(v)=i}\{v \in V(G) \mid c(v) = i\}{v∈V(G)∣c(v)=i} for i=1,…,ki = 1, \dots, ki=1,…,k . Each color class is a stable set (no two of its vertices are adjacent).

5. [Vertex Colorings] What is the chromatic number χ(G)\chi(G)χ(G) , and when is GGG kkk -chromatic?

   χ(G)\chi(G)χ(G) = the smallest kkk such that GGG is kkk -colorable. GGG is kkk -chromatic if k=χ(G)k = \chi(G)k=χ(G) . Equivalently, χ(G)\chi(G)χ(G) is the smallest number of stable sets into which V(G)V(G)V(G) can be partitioned.

6. [Vertex Colorings] What do α(G)\alpha(G)α(G) and ω(G)\omega(G)ω(G) denote?

   α(G)\alpha(G)α(G) = size of a largest stable set, ω(G)\omega(G)ω(G) = size of a largest clique in GGG . ω(G)\omega(G)ω(G) is the clique number of GGG .

7. [Vertex Colorings] Which lower bound on χ(G)\chi(G)χ(G) involves α(G)\alpha(G)α(G) (size of a largest stable set)?

   χ(G)≥∣V(G)∣α(G)\boldsymbol{\chi(G) \ge \dfrac{|V(G)|}{\alpha(G)}}χ(G)≥α(G)∣V(G)∣​ The χ(G)\chi(G)χ(G) color classes are stable sets, each with at most α(G)\alpha(G)α(G) vertices, and together they cover V(G)V(G)V(G) .

8. [Vertex Colorings] Which lower bound on χ(G)\chi(G)χ(G) involves ω(G)\omega(G)ω(G) (size of a largest clique)?

   χ(G)≥ω(G)\boldsymbol{\chi(G) \ge \omega(G)}χ(G)≥ω(G) All vertices of a clique must get different colors.

9. [Vertex Colorings] Which upper bound on χ(G)\chi(G)χ(G) holds for every graph GGG , with Δ(G)\Delta(G)Δ(G) the maximum degree?

   χ(G)≤Δ(G)+1\boldsymbol{\chi(G) \le \Delta(G) + 1}χ(G)≤Δ(G)+1 Proof by a greedy algorithm: go through the vertices in any order and give each vertex the first color not yet used at one of its neighbors.

10. [Vertex Colorings] Greedy coloring: traverse the vertices of GGG in any order and give each vertex vvv the first color not yet used at a neighbor of vvv .Why does the greedy coloring use at most Δ(G)+1\Delta(G) + 1Δ(G)+1 colors?

    Each vertex has at most Δ(G)\Delta(G)Δ(G) neighbors, so at most Δ(G)\Delta(G)Δ(G) of the colors 1,…,Δ(G)+11, \dots, \Delta(G) + 11,…,Δ(G)+1 are blocked.

11. [Vertex Colorings] Can χ(G)\chi(G)χ(G) be much smaller than Δ(G)\Delta(G)Δ(G) (the maximum degree)? Give an example.

    Yes: the star K1,n−1K_{1,n-1}K1,n−1​ has χ=2\chi = 2χ=2 but Δ=n−1\Delta = n - 1Δ=n−1 .

12. [Vertex Colorings] Name two families of connected graphs with χ(G)=Δ(G)+1\chi(G) = \Delta(G) + 1χ(G)=Δ(G)+1 .

    Complete graphs and odd cycles. χ(Kn)=n=Δ(Kn)+1\chi(K_n) = n = \Delta(K_n) + 1χ(Kn​)=n=Δ(Kn​)+1 and χ(C2k+1)=3=Δ+1\chi(C_{2k+1}) = 3 = \Delta + 1χ(C2k+1​)=3=Δ+1 . By Brooks' Theorem these are the only connected ones.

13. [Vertex Colorings] Brooks' Theorem (1941) Let GGG be a connected graph that is neither a complete graph nor an odd cycle. Then χ(G)≤ ?\chi(G) \le \; ?χ(G)≤?

    χ(G)≤Δ(G)\boldsymbol{\chi(G) \le \Delta(G)}χ(G)≤Δ(G) Δ(G)\Delta(G)Δ(G) is the maximum degree of GGG .

14. [Vertex Colorings] Brooks' Theorem: a connected graph GGG that is neither complete nor an odd cycle has χ(G)≤Δ(G)\chi(G) \le \Delta(G)χ(G)≤Δ(G) .The proof takes a smallest counterexample GGG . Why does GGG have Δ(G)≥3\Delta(G) \ge 3Δ(G)≥3 ?

    Connected graphs with Δ≤2\Delta \le 2Δ≤2 are paths and cycles, and the ones that are not complete and not odd cycles (paths on ≥3\ge 3≥3 vertices, even cycles) have χ=2=Δ\chi = 2 = \Deltaχ=2=Δ . A counterexample has χ(G)=Δ(G)+1\chi(G) = \Delta(G) + 1χ(G)=Δ(G)+1 , using the greedy bound χ≤Δ+1\chi \le \Delta + 1χ≤Δ+1 .

15. [Vertex Colorings] Proof of Brooks' Theorem: GGG is a smallest counterexample (connected, not complete, not an odd cycle, χ(G)=Δ(G)+1\chi(G) = \Delta(G) + 1χ(G)=Δ(G)+1 ), and vvv is a vertex of degree Δ(G)\Delta(G)Δ(G) .Why does vvv have two neighbors u,wu, wu,w that are not adjacent?

    Otherwise vvv and its neighbors form a KΔ+1K_{\Delta+1}KΔ+1​ that no edge leaves, so by connectivity GGG would be complete. Each neighbor of vvv already has degree Δ(G)\Delta(G)Δ(G) inside that clique.

16. [Vertex Colorings] Proof of Brooks' Theorem: GGG is a smallest counterexample, vvv has degree Δ(G)≥3\Delta(G) \ge 3Δ(G)≥3 , and u,wu, wu,w are nonadjacent neighbors of vvv .Case 1: G−{u,w}G - \{u, w\}G−{u,w} is connected. How is a Δ(G)\Delta(G)Δ(G) -coloring built?

    Color u,wu, wu,w with color 1, take a spanning tree TTT of G−{u,w}G - \{u, w\}G−{u,w} , and repeatedly color greedily a leaf x≠vx \ne vx=v of TTT and remove it from TTT . Color vvv last. Greedily: xxx gets the smallest color not used at its neighbors in GGG .

17. [Vertex Colorings] Brooks' proof, Case 1: u,wu, wu,w are nonadjacent neighbors of a vertex vvv of degree Δ(G)\Delta(G)Δ(G) , both get color 1; then leaves x≠vx \ne vx=v of a spanning tree TTT of G−{u,w}G - \{u, w\}G−{u,w} are colored greedily and removed from TTT , and vvv is colored last.Why are Δ(G)\Delta(G)Δ(G) colors enough, for each xxx and for vvv ?

    Each xxx still has an uncolored neighbor (its neighbor in TTT ), so at most Δ(G)−1\Delta(G) - 1Δ(G)−1 neighbors are colored. At vvv , the neighbors uuu and www share a color, so its Δ(G)\Delta(G)Δ(G) neighbors use at most Δ(G)−1\Delta(G) - 1Δ(G)−1 colors.

18. [Vertex Colorings] Brooks' proof, Case 2: u,wu, wu,w are nonadjacent neighbors of a vertex vvv of degree Δ(G)≥3\Delta(G) \ge 3Δ(G)≥3 , and G−{u,w}G - \{u, w\}G−{u,w} is disconnected. A1A_1A1​ is a component of G−{u,w}G - \{u, w\}G−{u,w} , V1=V(A1)∪{u,w}V_1 = V(A_1) \cup \{u, w\}V1​=V(A1​)∪{u,w} , V2=V(G)∖V(A1)V_2 = V(G) \setminus V(A_1)V2​=V(G)∖V(A1​) .If both G[V1]G[V_1]G[V1​] and G[V2]G[V_2]G[V2​] have Δ(G)\Delta(G)Δ(G) -colorings in which u,wu, wu,w get different colors, how do you color GGG…

    Permute colors so that uuu gets 1 and www gets 2 in both, then combine the two colorings. V1∩V2={u,w}V_1 \cap V_2 = \{u, w\}V1​∩V2​={u,w} , and no edge joins V(A1)V(A_1)V(A1​) to V2∖{u,w}V_2 \setminus \{u, w\}V2​∖{u,w} . Each G[Vi]G[V_i]G[Vi​] is Δ(G)\Delta(G)Δ(G) -colorable by minimality of GGG (it is smaller and not complete, as uwuwuw is missing).

19. [Vertex Colorings] Brooks' proof, Case 2: u,wu, wu,w are nonadjacent, G−{u,w}G - \{u, w\}G−{u,w} is disconnected, V1=V(A1)∪{u,w}V_1 = V(A_1) \cup \{u, w\}V1​=V(A1​)∪{u,w} for a component A1A_1A1​ of G−{u,w}G - \{u, w\}G−{u,w} , V2=V(G)∖V(A1)V_2 = V(G) \setminus V(A_1)V2​=V(G)∖V(A1​) , Δ(G)≥3\Delta(G) \ge 3Δ(G)≥3 .Suppose every Δ(G)\Delta(G)Δ(G) -coloring of G[Vj]G[V_j]G[Vj​] gives uuu and www the same color. How does the proof finish?

    Then uuu and www have degree ≥Δ(G)−1\ge \Delta(G) - 1≥Δ(G)−1 in G[Vj]G[V_j]G[Vj​] , so degree ≤1\le 1≤1 in G[V3−j]G[V_{3-j}]G[V3−j​] , and there a Δ(G)\Delta(G)Δ(G) -coloring with u,wu, wu,w of the same color exists (they block at most 2 of ≥3\ge 3≥3 colors). Combine. If uuu had degree ≤Δ(G)−2\le \Delta(G) - 2≤Δ(G)−2 in G[Vj]G[V_j]G[Vj​] , uuu could be recolored to differ from www .

20. [Vertex Colorings] Five Color Theorem (Heawood, 1890). For every planar graph GGG : χ(G)≤ ?\chi(G) \le \; ?χ(G)≤?

    χ(G)≤5\boldsymbol{\chi(G) \le 5}χ(G)≤5 The proof by contracting an edge between two neighbors of a low-degree vertex is due to Kainen (1974).

21. [Vertex Colorings] Why does every planar graph GGG on nnn vertices have a vertex of degree at most 5?

    ∣E(G)∣≤3n−6|E(G)| \le 3n - 6∣E(G)∣≤3n−6 , so the degrees sum to 2∣E(G)∣≤6n−12<6n2|E(G)| \le 6n - 12 < 6n2∣E(G)∣≤6n−12<6n . If all degrees were ≥6\ge 6≥6 , the sum would be ≥6n\ge 6n≥6n .

22. [Vertex Colorings] Five Color Theorem proof: induction on n=∣V(G)∣n = |V(G)|n=∣V(G)∣ ; v0v_0v0​ is a vertex of degree at most 5, and ccc is a 5-coloring of G−v0G - v_0G−v0​ .When can v0v_0v0​ be colored directly, and what remains?

    When the neighbors of v0v_0v0​ use fewer than 5 colors. What remains: v0v_0v0​ has exactly 5 neighbors v1,…,v5v_1, \dots, v_5v1​,…,v5​ with all 5 colors.

23. [Vertex Colorings] Five Color Theorem proof: GGG is planar, v0v_0v0​ has exactly 5 neighbors, and they use all 5 colors in a 5-coloring of G−v0G - v_0G−v0​ .How does the proof get a 5-coloring of G−v0G - v_0G−v0​ that leaves a color free for v0v_0v0​ ?

    Two neighbors vi,vjv_i, v_jvi​,vj​ of v0v_0v0​ are nonadjacent (else K5⊆GK_5 \subseteq GK5​⊆G ); add the edge vivjv_iv_jvi​vj​ to G−v0G - v_0G−v0​ and contract it. By induction the result is 5-colorable, which gives a 5-coloring of G−v0G - v_0G−v0​ with vi,vjv_i, v_jvi​,vj​ of the same color. Then the 5 neighbors use at most 4 colors.

24. [Vertex Colorings] GGG is planar and vi,vjv_i, v_jvi​,vj​ are nonadjacent neighbors of a vertex v0v_0v0​ .Why is G−v0G - v_0G−v0​ plus the edge vivjv_iv_jvi​vj​ still planar?

    Draw the new edge along the path vi,v0,vjv_i, v_0, v_jvi​,v0​,vj​ , which is free once v0v_0v0​ is deleted. Equivalently, it is a minor of GGG (contract v0viv_0v_iv0​vi​ ).

25. [Vertex Colorings] What does the Four Color Theorem say, and who first proved it?

    Every planar graph has χ(G)≤4\chi(G) \le 4χ(G)≤4 . First proved by Appel and Haken in 1977. The proof is long and needs a computer.

26. [Vertex Colorings] In the proof of the Four Color Theorem, what is a configuration?

    A connected subgraph of a graph GGG , together with the degrees in GGG of its vertices.

27. [Vertex Colorings] When is a set MMM of configurations unavoidable? Give the simplest example.

    Every planar graph contains a configuration in MMM . Example: M∗M^*M∗ = six copies of K1K_1K1​ , the iii -th with demanded degree iii ( i=0,…,5i = 0, \dots, 5i=0,…,5 ). Unavoidable since every planar graph has a vertex of degree at most 5.

28. [Vertex Colorings] When is a configuration reducible (for the Four Color Theorem)?

    No smallest counterexample to the Four Color Theorem contains it.

29. [Vertex Colorings] Why is the configuration " K1K_1K1​ with a vertex of degree 3" reducible for the Four Color Theorem?

    Delete the degree-3 vertex, 4-color the smaller planar graph, and the 3 neighbors leave a fourth color for it. So a smallest counterexample has no vertex of degree 3.

30. [Vertex Colorings] What is the strategy of the proof of the Four Color Theorem, in terms of configurations?

    Find an unavoidable set of reducible configurations. A smallest counterexample would contain one of them (unavoidable), but cannot (reducible). For five colors, the set M∗M^*M∗ of single vertices of degree 0,…,50, \dots, 50,…,5 already works.

31. [Vertex Colorings] How many configurations did the proofs of the Four Color Theorem need?

    Appel–Haken: 1936, later reduced to 1476. Robertson et al. (1997): 633. Every one of these proofs needs a computer to check the configurations.

32. [Vertex Colorings] What is the complement G‾\overline{G}G of a graph GGG ?

    V(G‾)=V(G)V(\overline{G}) = V(G)V(G)=V(G) and E(G‾)=(V(G)2)∖E(G)E(\overline{G}) = \binom{V(G)}{2} \setminus E(G)E(G)=(2V(G)​)∖E(G) : two vertices are adjacent in G‾\overline{G}G iff they are not adjacent in GGG .

33. [Vertex Colorings] Nordhaus–Gaddum (1956). GGG has nnn vertices. Bound χ(G)+χ(G‾)\chi(G) + \chi(\overline{G})χ(G)+χ(G) from below and above.

    2n≤χ(G)+χ(G‾)≤n+1\boldsymbol{2\sqrt{n} \le \chi(G) + \chi(\overline{G}) \le n + 1}2n​≤χ(G)+χ(G)≤n+1 So χ(G)\chi(G)χ(G) and χ(G‾)\chi(\overline{G})χ(G) cannot both be very large (of order nnn ), nor both very small.

34. [Vertex Colorings] Nordhaus–Gaddum (1956). GGG has nnn vertices. Bound χ(G)⋅χ(G‾)\chi(G) \cdot \chi(\overline{G})χ(G)⋅χ(G) from below and above.

    n≤χ(G) χ(G‾)≤(n+12)2\boldsymbol{n \le \chi(G)\,\chi(\overline{G}) \le \left(\frac{n+1}{2}\right)^2}n≤χ(G)χ(G)≤(2n+1​)2

35. [Vertex Colorings] GGG has nnn vertices. Why is χ(G) χ(G‾)≥n\chi(G)\,\chi(\overline{G}) \ge nχ(G)χ(G)≥n ?

    Some color class of an optimal coloring of GGG has ≥n/χ(G)\ge n / \chi(G)≥n/χ(G) vertices, and it is a clique in G‾\overline{G}G , so χ(G‾)≥n/χ(G)\chi(\overline{G}) \ge n / \chi(G)χ(G)≥n/χ(G) .

36. [Vertex Colorings] GGG has nnn vertices and χ(G) χ(G‾)≥n\chi(G)\,\chi(\overline{G}) \ge nχ(G)χ(G)≥n .Why does χ(G)+χ(G‾)≥2n\chi(G) + \chi(\overline{G}) \ge 2\sqrt{n}χ(G)+χ(G)≥2n​ follow?

    (χ(G)−χ(G‾))2≥0(\chi(G) - \chi(\overline{G}))^2 \ge 0(χ(G)−χ(G))2≥0 gives (χ(G)+χ(G‾))2≥4χ(G)χ(G‾)≥4n(\chi(G) + \chi(\overline{G}))^2 \ge 4\chi(G)\chi(\overline{G}) \ge 4n(χ(G)+χ(G))2≥4χ(G)χ(G)≥4n . The AM–GM inequality.

37. [Vertex Colorings] Claim: χ(G)+χ(G‾)≤n+1\chi(G) + \chi(\overline{G}) \le n + 1χ(G)+χ(G)≤n+1 for every graph GGG on nnn vertices, by induction on nnn .For a vertex vvv , how does the induction step go?

    Deleting vvv lowers each of χ(G)\chi(G)χ(G) , χ(G‾)\chi(\overline{G})χ(G) by at most 1. If one drops by less, done by induction. If both drop by 1, then deg⁡Gv≥χ(G−v)\deg_G v \ge \chi(G - v)degG​v≥χ(G−v) and deg⁡G‾v≥χ(G‾−v)\deg_{\overline{G}} v \ge \chi(\overline{G} - v)degG​v≥χ(G−v) , which sum to n−1n - 1n−1 . So χ(G−v)+χ(G‾−v)≤n−1\chi(G - v) + \chi(\overline{G} - v) \le n - 1χ(G−v)+χ(G−v)≤n−1 and χ(G)+χ(G‾)≤n+1\chi(G) + \chi(\overline{G}) \le n + 1χ(G)+χ(G)≤n+1 .

38. [Vertex Colorings] If χ(G)=χ(G−v)+1\chi(G) = \chi(G - v) + 1χ(G)=χ(G−v)+1 for a vertex vvv , why is deg⁡Gv≥χ(G−v)\deg_G v \ge \chi(G - v)degG​v≥χ(G−v) ?

    Otherwise the neighbors of vvv miss one of the χ(G−v)\chi(G - v)χ(G−v) colors of an optimal coloring of G−vG - vG−v , and vvv could take that color. Then χ(G)=χ(G−v)\chi(G) = \chi(G - v)χ(G)=χ(G−v) .

39. [Vertex Colorings] GGG has nnn vertices and χ(G)+χ(G‾)≤n+1\chi(G) + \chi(\overline{G}) \le n + 1χ(G)+χ(G)≤n+1 .Why does χ(G) χ(G‾)≤(n+12)2\chi(G)\,\chi(\overline{G}) \le \left(\frac{n+1}{2}\right)^2χ(G)χ(G)≤(2n+1​)2 follow?

    4χ(G)χ(G‾)≤(χ(G)+χ(G‾))2≤(n+1)24\chi(G)\chi(\overline{G}) \le (\chi(G) + \chi(\overline{G}))^2 \le (n + 1)^24χ(G)χ(G)≤(χ(G)+χ(G))2≤(n+1)2 .

40. [Vertex Colorings] Is a large chromatic number always caused by a large clique? State the result.

    No: for every k≥1k \ge 1k≥1 there is a graph GkG_kGk​ with χ(Gk)=k\chi(G_k) = kχ(Gk​)=k and ω(Gk)≤2\omega(G_k) \le 2ω(Gk​)≤2 (no triangles). So the clique number ω\omegaω can be a very bad lower bound for χ\chiχ .

41. [Vertex Colorings] Goal: triangle-free graphs GkG_kGk​ with χ(Gk)=k\chi(G_k) = kχ(Gk​)=k , built recursively; G1=K1G_1 = K_1G1​=K1​ .How is GkG_kGk​ built from G1,…,Gk−1G_1, \dots, G_{k-1}G1​,…,Gk−1​ ?

    Take disjoint copies of G1,…,Gk−1G_1, \dots, G_{k-1}G1​,…,Gk−1​ , and add a stable set AkA_kAk​ with one new vertex for each tuple (v1,…,vk−1)(v_1, \dots, v_{k-1})(v1​,…,vk−1​) , vi∈V(Gi)v_i \in V(G_i)vi​∈V(Gi​) , joined to v1,…,vk−1v_1, \dots, v_{k-1}v1​,…,vk−1​ . So ∣Ak∣=∣V(G1)∣⋯∣V(Gk−1)∣|A_k| = |V(G_1)| \cdots |V(G_{k-1})|∣Ak​∣=∣V(G1​)∣⋯∣V(Gk−1​)∣ . Example: G2=K2G_2 = K_2G2​=K2​ and G3=C5G_3 = C_5G3​=C5​ .

42. [Vertex Colorings] GkG_kGk​ : disjoint copies of G1,…,Gk−1G_1, \dots, G_{k-1}G1​,…,Gk−1​ plus a stable set AkA_kAk​ with one vertex for each tuple (v1,…,vk−1)(v_1, \dots, v_{k-1})(v1​,…,vk−1​) , vi∈V(Gi)v_i \in V(G_i)vi​∈V(Gi​) , joined to v1,…,vk−1v_1, \dots, v_{k-1}v1​,…,vk−1​ .Why has GkG_kGk​ no triangle (given that G1,…,Gk−1G_1, \dots, G_{k-1}G1​,…,Gk−1​ have none)?

    A vertex of AkA_kAk​ has its neighbors in different copies GiG_iGi​ , which are not adjacent to each other, and AkA_kAk​ is stable. So a triangle would lie inside one GiG_iGi​ .

43. [Vertex Colorings] GkG_kGk​ : disjoint copies of G1,…,Gk−1G_1, \dots, G_{k-1}G1​,…,Gk−1​ plus a stable set AkA_kAk​ with one vertex for each tuple (v1,…,vk−1)(v_1, \dots, v_{k-1})(v1​,…,vk−1​) , vi∈V(Gi)v_i \in V(G_i)vi​∈V(Gi​) , joined to v1,…,vk−1v_1, \dots, v_{k-1}v1​,…,vk−1​ . By induction, χ(Gi)=i\chi(G_i) = iχ(Gi​)=i .Why is GkG_kGk​ kkk -colorable?

    Color all copies G1,…,Gk−1G_1, \dots, G_{k-1}G1​,…,Gk−1​ with colors 1,…,k−11, \dots, k - 11,…,k−1 , and give all of AkA_kAk​ color kkk . AkA_kAk​ is a stable set.

44. [Vertex Colorings] GkG_kGk​ : disjoint copies of G1,…,Gk−1G_1, \dots, G_{k-1}G1​,…,Gk−1​ plus a stable set AkA_kAk​ with one vertex for each tuple (v1,…,vk−1)(v_1, \dots, v_{k-1})(v1​,…,vk−1​) , vi∈V(Gi)v_i \in V(G_i)vi​∈V(Gi​) , joined to v1,…,vk−1v_1, \dots, v_{k-1}v1​,…,vk−1​ . By induction, χ(Gi)=i\chi(G_i) = iχ(Gi​)=i .Why is GkG_kGk​ not (k−1)(k-1)(k−1) -colorable?

    In a (k−1)(k-1)(k−1) -coloring, pick vi∈Giv_i \in G_ivi​∈Gi​ with a color ci∉{c1,…,ci−1}c_i \notin \{c_1, \dots, c_{i-1}\}ci​∈/{c1​,…,ci−1​} for each iii (possible as GiG_iGi​ needs iii colors). The vertex of AkA_kAk​ for (v1,…,vk−1)(v_1, \dots, v_{k-1})(v1​,…,vk−1​) then sees all k−1k - 1k−1 colors.

45. [Vertex Colorings] Must a graph with large chromatic number contain short cycles?

    No: for every kkk there are graphs with χ(G)≥k\chi(G) \ge kχ(G)≥k and no cycle of length less than kkk . See Nešetřil and Rödl (1979) or Diestel (2005).

46. [Vertex Colorings] When is a subgraph HHH of GGG an induced subgraph?

    E(H)=E(G[V(H)])E(H) = E(G[V(H)])E(H)=E(G[V(H)]) : HHH contains every edge of GGG between its vertices.

47. [Vertex Colorings] When is a graph GGG perfect?

    χ(H)=ω(H)\chi(H) = \omega(H)χ(H)=ω(H) for every induced subgraph HHH of GGG . ω(H)\omega(H)ω(H) is the size of a largest clique of HHH .

48. [Vertex Colorings] Why do perfect graphs matter algorithmically?

    Maximum stable set, maximum clique and optimum vertex coloring, NP-hard in general, are polynomial-time solvable on perfect graphs. Grötschel, Lovász and Schrijver (1984).

49. [Vertex Colorings] Lovász (1972). A graph is perfect if and only if … ?

    α(H) ω(H)≥∣V(H)∣\alpha(H)\,\omega(H) \ge |V(H)|α(H)ω(H)≥∣V(H)∣ for every induced subgraph HHH . α\alphaα = size of a largest stable set, ω\omegaω = size of a largest clique.

50. [Vertex Colorings] Lovász: GGG is perfect iff α(H)ω(H)≥∣V(H)∣\alpha(H)\omega(H) \ge |V(H)|α(H)ω(H)≥∣V(H)∣ for every induced subgraph HHH .Why does perfect imply the inequality?

    χ(H)=ω(H)\chi(H) = \omega(H)χ(H)=ω(H) and always α(H)χ(H)≥∣V(H)∣\alpha(H)\chi(H) \ge |V(H)|α(H)χ(H)≥∣V(H)∣ . The χ(H)\chi(H)χ(H) color classes are stable sets of size at most α(H)\alpha(H)α(H) covering V(H)V(H)V(H) .

51. [Vertex Colorings] Lovász: GGG is perfect iff α(H)ω(H)≥∣V(H)∣\alpha(H)\omega(H) \ge |V(H)|α(H)ω(H)≥∣V(H)∣ for every induced subgraph HHH .For the converse, which graph GGG does the proof consider, and what do we know about it?

    A smallest non-perfect graph with α(H)ω(H)≥∣V(H)∣\alpha(H)\omega(H) \ge |V(H)|α(H)ω(H)≥∣V(H)∣ for all induced subgraphs HHH . So every proper induced subgraph of GGG is perfect. Write n=∣V(G)∣n = |V(G)|n=∣V(G)∣ , α=α(G)\alpha = \alpha(G)α=α(G) , ω=ω(G)\omega = \omega(G)ω=ω(G) . The goal is a contradiction n≥αω+1n \ge \alpha\omega + 1n≥αω+1 .

52. [Vertex Colorings] Lovász's proof: GGG is not perfect but every proper induced subgraph is; α=α(G)\alpha = \alpha(G)α=α(G) , ω=ω(G)\omega = \omega(G)ω=ω(G) .How does the proof get stable sets S0,…,SαωS_0, \dots, S_{\alpha\omega}S0​,…,Sαω​ with every vertex in exactly α\alphaα of them?

    S0S_0S0​ is a largest stable set; for each v∈S0v \in S_0v∈S0​ , G−vG - vG−v is perfect, so V(G)∖{v}V(G) \setminus \{v\}V(G)∖{v} splits into ω\omegaω stable sets (some possibly empty), as χ(G−v)=ω(G−v)≤ω\chi(G - v) = \omega(G - v) \le \omegaχ(G−v)=ω(G−v)≤ω . Take these α⋅ω\alpha \cdot \omegaα⋅ω sets plus S0S_0S0​ . A vertex outside S0S_0S0​ lies in one set per v∈S0v \in S_0v∈S0​ : α\alphaα sets. A vertex in S0S_0S0​ lies in S0S_0S0​ and in one set per other v∈S0v \in S_0v∈S0​ : 1+(α−1)1 + (\alph…

53. [Vertex Colorings] Lovász's proof: GGG is not perfect but every proper induced subgraph is; ω=ω(G)\omega = \omega(G)ω=ω(G) ; SiS_iSi​ is a stable set.Why is there a clique CiC_iCi​ of size ω\omegaω with Ci∩Si=∅C_i \cap S_i = \emptysetCi​∩Si​=∅ ?

    Otherwise ω(G)≥ω(G−Si)+1=χ(G−Si)+1≥χ(G)\omega(G) \ge \omega(G - S_i) + 1 = \chi(G - S_i) + 1 \ge \chi(G)ω(G)≥ω(G−Si​)+1=χ(G−Si​)+1≥χ(G) , so χ(G)=ω(G)\chi(G) = \omega(G)χ(G)=ω(G) and GGG would be perfect. G−SiG - S_iG−Si​ is perfect, and SiS_iSi​ can take one extra color.

54. [Vertex Colorings] Lovász's proof: stable sets S0,…,SαωS_0, \dots, S_{\alpha\omega}S0​,…,Sαω​ cover every vertex exactly α\alphaα times; CiC_iCi​ is a clique of size ω\omegaω disjoint from SiS_iSi​ .Why is ∣Ci∩Sj∣=1|C_i \cap S_j| = 1∣Ci​∩Sj​∣=1 for all i≠ji \ne ji=j ?

    A clique meets a stable set in at most one vertex, and CiC_iCi​ has ω⋅α\omega \cdot \alphaω⋅α incidences with the sets SjS_jSj​ in total, spread over the αω\alpha\omegaαω sets SjS_jSj​ with j≠ij \ne ij=i .

55. [Vertex Colorings] Lovász's proof: stable sets S0,…,SαωS_0, \dots, S_{\alpha\omega}S0​,…,Sαω​ and cliques C0,…,CαωC_0, \dots, C_{\alpha\omega}C0​,…,Cαω​ in GGG ( nnn vertices) with ∣Ci∩Sj∣=1|C_i \cap S_j| = 1∣Ci​∩Sj​∣=1 for i≠ji \ne ji=j and Ci∩Si=∅C_i \cap S_i = \emptysetCi​∩Si​=∅ .How does the proof reach a contradiction?

    With MMM , NNN the (αω+1)×n(\alpha\omega + 1) \times n(αω+1)×n incidence matrices of the SiS_iSi​ and the CiC_iCi​ : MNT=J−IMN^{T} = J - IMNT=J−I , which has rank αω+1\alpha\omega + 1αω+1 . So n≥αω+1n \ge \alpha\omega + 1n≥αω+1 , contradicting α(G)ω(G)≥n\alpha(G)\omega(G) \ge nα(G)ω(G)≥n . JJJ is the all-ones matrix; entry (i,j)(i, j)(i,j) of MNTMN^{T}MNT is ∣Si∩Cj∣|S_i \cap C_j|∣Si​∩Cj​∣ .

56. [Vertex Colorings] Weak perfect graph theorem (Lovász, 1972). A graph GGG is perfect if and only if … ?

    G‾\overline{G}G is perfect.

57. [Vertex Colorings] Lovász: GGG is perfect iff α(H)ω(H)≥∣V(H)∣\alpha(H)\omega(H) \ge |V(H)|α(H)ω(H)≥∣V(H)∣ for every induced subgraph HHH .Why does it follow that GGG is perfect iff its complement G‾\overline{G}G is?

    Complementing swaps α\alphaα and ω\omegaω , and the induced subgraphs of G‾\overline{G}G are the complements of those of GGG . The condition αω≥∣V∣\alpha\omega \ge |V|αω≥∣V∣ is symmetric.

58. [Vertex Colorings] Name three classes of perfect graphs.

    Bipartite graphs, line graphs of bipartite graphs, interval graphs (and the complements of all of these). Complements are perfect by the weak perfect graph theorem.

59. [Vertex Colorings] Why are bipartite graphs perfect?

    Every induced subgraph HHH is bipartite, so χ(H)=ω(H)\chi(H) = \omega(H)χ(H)=ω(H) : both are 2 if HHH has an edge, 1 otherwise (for HHH nonempty).

60. [Vertex Colorings] Strong perfect graph theorem (Chudnovsky et al., 2006). A graph is perfect if and only if … ?

    It contains neither an odd cycle of length ≥5\ge 5≥5 nor the complement of one as an induced subgraph.

61. [Vertex Colorings] Why does the strong perfect graph theorem imply the weak one ( GGG perfect iff G‾\overline{G}G perfect)?

    The forbidden induced subgraphs (odd cycles of length ≥5\ge 5≥5 and their complements) are closed under complementation. GGG contains one of them as an induced subgraph iff G‾\overline{G}G does.

62. [Vertex Colorings] What is a Berge graph, and how fast can perfection be tested?

    A graph with no odd cycle of length ≥5\ge 5≥5 and no complement of one as an induced subgraph. Testing takes O(∣V(G)∣9)O(|V(G)|^9)O(∣V(G)∣9) time. Chudnovsky et al. (2005) gave the test for Berge graphs before the strong perfect graph theorem showed Berge = perfect.

63. [List-Colorings] Every vertex vvv of GGG has a set CvC_vCv​ (its color-list). What is a (feasible) vertex-list-coloring?

    A map ccc with c(v)∈Cvc(v) \in C_vc(v)∈Cv​ for every vertex vvv and c(v)≠c(w)c(v) \ne c(w)c(v)=c(w) for every edge {v,w}\{v, w\}{v,w} .

64. [List-Colorings] What is the list-chromatic number χl(G)\chi_l(G)χl​(G) ?

    The smallest kkk such that for every choice of color-lists of size at least kkk , a vertex-list-coloring exists.

65. [List-Colorings] How do χ(G)\chi(G)χ(G) and χl(G)\chi_l(G)χl​(G) (list-chromatic number) compare, and why?

    χ(G)≤χl(G)\boldsymbol{\chi(G) \le \chi_l(G)}χ(G)≤χl​(G) Giving every vertex the list {1,…,χl(G)}\{1, \dots, \chi_l(G)\}{1,…,χl​(G)} yields an ordinary coloring.

66. [List-Colorings] How large is χl(Kk,kk)\chi_l(K_{k,k^k})χl​(Kk,kk​) compared with χ(Kk,kk)=2\chi(K_{k,k^k}) = 2χ(Kk,kk​)=2 ?

    χl(Kk,kk)>k\boldsymbol{\chi_l(K_{k,k^k}) > k}χl​(Kk,kk​)>k So the list-chromatic number can be much larger than the chromatic number.

67. [List-Colorings] Goal: color-lists of size kkk on Kk,kkK_{k,k^k}Kk,kk​ , with sides A={a1,…,ak}A = \{a_1, \dots, a_k\}A={a1​,…,ak​} and BBB ( ∣B∣=kk|B| = k^k∣B∣=kk ), that admit no list coloring.Which lists does the proof choose?

    The aia_iai​ get pairwise disjoint lists Cai={(i−1)k+1,…,ik}C_{a_i} = \{(i-1)k + 1, \dots, ik\}Cai​​={(i−1)k+1,…,ik} ; the vertices of BBB get, one each, all kkk^kkk sets containing exactly one color from each CaiC_{a_i}Cai​​ . All colors come from {1,…,k2}\{1, \dots, k^2\}{1,…,k2} .

68. [List-Colorings] Kk,kkK_{k,k^k}Kk,kk​ : a1,…,aka_1, \dots, a_ka1​,…,ak​ have disjoint lists CaiC_{a_i}Cai​​ of size kkk ; the kkk^kkk vertices of the other side get all sets with exactly one color from each CaiC_{a_i}Cai​​ .Why is there no list coloring?

    Whatever colors c1,…,ckc_1, \dots, c_kc1​,…,ck​ the aia_iai​ get, {c1,…,ck}\{c_1, \dots, c_k\}{c1​,…,ck​} is the list of some b∈Bb \in Bb∈B , and bbb is adjacent to all aia_iai​ , so no color is left for bbb .

69. [List-Colorings] Give color-lists of size 2 on K2,4K_{2,4}K2,4​ with no list coloring.

    a1:{1,2}a_1: \{1, 2\}a1​:{1,2} , a2:{3,4}a_2: \{3, 4\}a2​:{3,4} ; the other side: {1,3},{1,4},{2,3},{2,4}\{1, 3\}, \{1, 4\}, \{2, 3\}, \{2, 4\}{1,3},{1,4},{2,3},{2,4} . Any choice c(a1)∈{1,2}c(a_1) \in \{1, 2\}c(a1​)∈{1,2} , c(a2)∈{3,4}c(a_2) \in \{3, 4\}c(a2​)∈{3,4} uses up some list on the other side completely. So χl(K2,4)>2=χ(K2,4)\chi_l(K_{2,4}) > 2 = \chi(K_{2,4})χl​(K2,4​)>2=χ(K2,4​) .

70. [List-Colorings] Which upper bound on χl(G)\chi_l(G)χl​(G) (list-chromatic number) holds for every graph, and why?

    χl(G)≤Δ(G)+1\boldsymbol{\chi_l(G) \le \Delta(G) + 1}χl​(G)≤Δ(G)+1 The greedy procedure works: each vertex has at most Δ(G)\Delta(G)Δ(G) colored neighbors, and its list has Δ(G)+1\Delta(G) + 1Δ(G)+1 colors.

71. [List-Colorings] Does Brooks' Theorem ( χ(G)≤Δ(G)\chi(G) \le \Delta(G)χ(G)≤Δ(G) for connected GGG neither complete nor an odd cycle) hold for list colorings?

    Yes: χl(G)≤Δ(G)\chi_l(G) \le \Delta(G)χl​(G)≤Δ(G) for such GGG . Vizing (1976) and independently Erdős, Rubin and Taylor (1979).

72. [List-Colorings] Thomassen (1994). For every planar graph GGG : χl(G)≤ ?\chi_l(G) \le \; ?χl​(G)≤?

    χl(G)≤5\boldsymbol{\chi_l(G) \le 5}χl​(G)≤5 This is best possible: some planar graphs have χl(G)=5\chi_l(G) = 5χl​(G)=5 . So the Four Color Theorem does not carry over to list colorings.

73. [List-Colorings] In Thomassen's proof that planar graphs have χl≤5\chi_l \le 5χl​≤5 , what is a nearly triangulated graph, and why may we assume GGG is one?

    A connected graph with a planar embedding where every region is bounded by a cycle, and every region except possibly the unbounded one by a triangle. Adding edges can only increase χl\chi_lχl​ , so we may add edges until GGG is nearly triangulated.

74. [List-Colorings] Thomassen's proof ( χl≤5\chi_l \le 5χl​≤5 for planar graphs) proves a stronger statement by induction. GGG is nearly triangulated, BBB is the cycle bounding the unbounded region. Which list conditions guarantee a list coloring?

    Two neighbors x,yx, yx,y on BBB have Cx={α}C_x = \{\alpha\}Cx​={α} , Cy={β}C_y = \{\beta\}Cy​={β} with α≠β\alpha \ne \betaα=β ; other vertices on BBB have ∣Cv∣≥3|C_v| \ge 3∣Cv​∣≥3 ; vertices not on BBB have ∣Cv∣≥5|C_v| \ge 5∣Cv​∣≥5 .

75. [List-Colorings] Thomassen's statement: nearly triangulated GGG , outer cycle BBB ; two neighbors x,yx, yx,y on BBB with Cx={α}C_x = \{\alpha\}Cx​={α} , Cy={β}C_y = \{\beta\}Cy​={β} , α≠β\alpha \ne \betaα=β ; ∣Cv∣≥3|C_v| \ge 3∣Cv​∣≥3 on the rest of BBB ; ∣Cv∣≥5|C_v| \ge 5∣Cv​∣≥5 off BBB . Then a list coloring exists.Why does this give χl(G)≤5\chi_l(G) \le 5χl​(G)≤5 for planar GGG ?

    Given lists of size 5, pick an edge xyxyxy of BBB , choose α∈Cx\alpha \in C_xα∈Cx​ and β∈Cy∖{α}\beta \in C_y \setminus \{\alpha\}β∈Cy​∖{α} , and shrink Cx={α}C_x = \{\alpha\}Cx​={α} , Cy={β}C_y = \{\beta\}Cy​={β} . All other lists have size 5≥35 \ge 35≥3 .

76. [List-Colorings] Thomassen's statement: nearly triangulated GGG , outer cycle BBB ; two neighbors x,yx, yx,y on BBB with Cx={α}C_x = \{\alpha\}Cx​={α} , Cy={β}C_y = \{\beta\}Cy​={β} , α≠β\alpha \ne \betaα=β ; ∣Cv∣≥3|C_v| \ge 3∣Cv​∣≥3 on the rest of BBB ; ∣Cv∣≥5|C_v| \ge 5∣Cv​∣≥5 off BBB . Then a list coloring exists.Why does it hold for ∣V(G)∣=3|V(G)| = 3∣V(G)∣=3 ?

    The third vertex vvv has ∣Cv∣≥3|C_v| \ge 3∣Cv​∣≥3 , so some color in CvC_vCv​ differs from α\alphaα and β\betaβ .

77. [List-Colorings] Thomassen's statement: nearly triangulated GGG , outer cycle BBB ; two neighbors x,yx, yx,y on BBB with Cx={α}C_x = \{\alpha\}Cx​={α} , Cy={β}C_y = \{\beta\}Cy​={β} , α≠β\alpha \ne \betaα=β ; ∣Cv∣≥3|C_v| \ge 3∣Cv​∣≥3 on the rest of BBB ; ∣Cv∣≥5|C_v| \ge 5∣Cv​∣≥5 off BBB . Then a list coloring exists. Proof by induction on ∣V(G)∣|V(G)|∣V(G)∣ .Case 1: BBB has a chord uvuvuv (an edge between two vertices of BBB that are not neighbors on BBB ). How does the induction step go?

    The chord splits GGG into G1G_1G1​ (containing the edge xyxyxy ) and G2G_2G2​ , sharing only u,vu, vu,v . Color G1G_1G1​ by induction, then color G2G_2G2​ by induction with the lists of u,vu, vu,v reduced to their colors. In G2G_2G2​ , the precolored u,vu, vu,v play the roles of x,yx, yx,y : they are neighbors on its outer cycle and have different colors.

78. [List-Colorings] Thomassen's statement: nearly triangulated GGG , outer cycle BBB ; two neighbors x,yx, yx,y on BBB with Cx={α}C_x = \{\alpha\}Cx​={α} , Cy={β}C_y = \{\beta\}Cy​={β} , α≠β\alpha \ne \betaα=β ; ∣Cv∣≥3|C_v| \ge 3∣Cv​∣≥3 on the rest of BBB ; ∣Cv∣≥5|C_v| \ge 5∣Cv​∣≥5 off BBB . Then a list coloring exists. Proof by induction on ∣V(G)∣|V(G)|∣V(G)∣ .Case 2: BBB has no chord. Let vvv be the neighbor of xxx on BBB other than yyy , and www the neighbor of vvv on BBB other than xxx . What…

    Pick two colors γ,δ∈Cv∖{α}\gamma, \delta \in C_v \setminus \{\alpha\}γ,δ∈Cv​∖{α} , remove γ\gammaγ and δ\deltaδ from the lists of all neighbors of vvv except www and xxx , and color G−vG - vG−v by induction. Then vvv gets whichever of γ,δ\gamma, \deltaγ,δ the vertex www does not use.

79. [List-Colorings] Thomassen's proof, Case 2 (no chord of the outer cycle BBB ): vvv is a neighbor of xxx on BBB , www the other neighbor of vvv on BBB ; γ,δ\gamma, \deltaγ,δ are removed from the lists of the neighbors of vvv other than w,xw, xw,x , and G−vG - vG−v is colored by induction.Why does G−vG - vG−v satisfy the list conditions (size ≥3\ge 3≥3 on its outer cycle)?

    The neighbors of vvv other than w,xw, xw,x were not on BBB (no chord), so they had ≥5\ge 5≥5 colors, and still have ≥3\ge 3≥3 . Removing vvv puts them on the outer cycle of G−vG - vG−v . G−vG - vG−v is still nearly triangulated.

80. [List-Colorings] Thomassen's proof, Case 2: vvv is the neighbor of xxx on the outer cycle other than yyy ; Cx={α}C_x = \{\alpha\}Cx​={α} ; γ,δ∈Cv∖{α}\gamma, \delta \in C_v \setminus \{\alpha\}γ,δ∈Cv​∖{α} were removed from the lists of the neighbors of vvv other than w,xw, xw,x , and G−vG - vG−v is list-colored.Why can vvv be colored?

    Among the neighbors of vvv , only www can use γ\gammaγ or δ\deltaδ ( xxx has α\alphaα ), so one of γ,δ\gamma, \deltaγ,δ is free.

81. [List-Colorings] Thomassen (2003). Which bound on χl(G)\chi_l(G)χl​(G) holds for planar graphs of girth at least 5?

    χl(G)≤3\boldsymbol{\chi_l(G) \le 3}χl​(G)≤3 Girth = length of a shortest cycle. The proof is similar to the proof of χl≤5\chi_l \le 5χl​≤5 for planar graphs.

82. [Edge Colorings] What is a (feasible) kkk -edge coloring of a graph GGG ?

    A map c:E(G)→{1,…,k}c : E(G) \to \{1, \dots, k\}c:E(G)→{1,…,k} with c(e1)≠c(e2)c(e_1) \ne c(e_2)c(e1​)=c(e2​) whenever e1∩e2≠∅e_1 \cap e_2 \ne \emptysete1​∩e2​=∅ . Edges sharing an endpoint get different colors. GGG is kkk -edge-colorable if such a coloring exists.

83. [Edge Colorings] What is the chromatic index χ′(G)\chi&#x27;(G)χ′(G) , and what are the color classes of an edge coloring?

    χ′(G)\chi&#x27;(G)χ′(G) = the smallest kkk such that GGG is kkk -edge-colorable. Color classes: the sets {e∈E(G)∣c(e)=i}\{e \in E(G) \mid c(e) = i\}{e∈E(G)∣c(e)=i} . Also called the edge-chromatic number. Each color class is a matching.

84. [Edge Colorings] How is edge coloring a special case of vertex coloring?

    χ′(G)=χ(LG)\chi&#x27;(G) = \chi(L_G)χ′(G)=χ(LG​) , for the line graph LGL_GLG​ : vertices E(G)E(G)E(G) , two edges adjacent iff they share an endpoint.

85. [Edge Colorings] Vizing's Theorem (1964). Bound χ′(G)\chi&#x27;(G)χ′(G) (chromatic index) for every graph GGG .

    Δ(G)≤χ′(G)≤Δ(G)+1\boldsymbol{\Delta(G) \le \chi&#x27;(G) \le \Delta(G) + 1}Δ(G)≤χ′(G)≤Δ(G)+1 The lower bound is trivial: the Δ(G)\Delta(G)Δ(G) edges at a vertex of maximum degree need different colors.

86. [Edge Colorings] Vizing: χ′(G)≤Δ(G)+1\chi&#x27;(G) \le \Delta(G) + 1χ′(G)≤Δ(G)+1 , by induction on the number of edges. Remove an edge e={x,y}e = \{x, y\}e={x,y} and take an edge coloring ccc of G−eG - eG−e with Δ(G)+1\Delta(G) + 1Δ(G)+1 colors.Why does every vertex vvv have a color λ(v)\lambda(v)λ(v) missing at vvv ?

    At most Δ(G)\Delta(G)Δ(G) edges meet vvv , but there are Δ(G)+1\Delta(G) + 1Δ(G)+1 colors.

87. [Edge Colorings] Vizing's proof: ccc colors G−{x,y}G - \{x, y\}G−{x,y} with Δ(G)+1\Delta(G) + 1Δ(G)+1 colors; λ(v)\lambda(v)λ(v) is a color missing at vvv .Which sequence y0,…,yty_0, \dots, y_ty0​,…,yt​ of neighbors of xxx does the proof choose?

    A maximal sequence of distinct neighbors with y0=yy_0 = yy0​=y and c({x,yi})=λ(yi−1)c(\{x, y_i\}) = \lambda(y_{i-1})c({x,yi​})=λ(yi−1​) : each edge xyixy_ixyi​ has the color missing at the previous vertex. Maximal: if a neighbor zzz of xxx has c({x,z})=λ(yt)c(\{x, z\}) = \lambda(y_t)c({x,z})=λ(yt​) , then zzz is already among y0,…,yty_0, \dots, y_ty0​,…,yt​ .

88. [Edge Colorings] Vizing's proof: xy0xy_0xy0​ is uncolored; y0,…,yty_0, \dots, y_ty0​,…,yt​ are neighbors of xxx with c({x,yi})=λ(yi−1)c(\{x, y_i\}) = \lambda(y_{i-1})c({x,yi​})=λ(yi−1​) , where λ(v)\lambda(v)λ(v) is a color missing at vvv .Case 1: λ(yt)\lambda(y_t)λ(yt​) is also missing at xxx . How is GGG colored?

    Shift: recolor {x,yi−1}\{x, y_{i-1}\}{x,yi−1​} with c({x,yi})c(\{x, y_i\})c({x,yi​}) for i=1,…,ti = 1, \dots, ti=1,…,t , and color {x,yt}\{x, y_t\}{x,yt​} with λ(yt)\lambda(y_t)λ(yt​) . Each yi−1y_{i-1}yi−1​ receives its missing color λ(yi−1)\lambda(y_{i-1})λ(yi−1​) ; xxx receives the extra color λ(yt)\lambda(y_t)λ(yt​) .

89. [Edge Colorings] Vizing's proof: xy0xy_0xy0​ is uncolored; y0,…,yty_0, \dots, y_ty0​,…,yt​ is a maximal sequence of neighbors of xxx with c({x,yi})=λ(yi−1)c(\{x, y_i\}) = \lambda(y_{i-1})c({x,yi​})=λ(yi−1​) ; λ(v)\lambda(v)λ(v) is a color missing at vvv .Case 2: λ(yt)\lambda(y_t)λ(yt​) is not missing at xxx . Which structure does the proof use?

    λ(yt)=c({x,ys})\lambda(y_t) = c(\{x, y_s\})λ(yt​)=c({x,ys​}) for some s∈{1,…,t−1}s \in \{1, \dots, t-1\}s∈{1,…,t−1} . Let HHH be the subgraph of edges colored λ(x)\lambda(x)λ(x) or λ(yt)\lambda(y_t)λ(yt​) , and PPP a maximal path in HHH starting at yty_tyt​ . Δ(H)≤2\Delta(H) \le 2Δ(H)≤2 , and yty_tyt​ has degree ≤1\le 1≤1 in HHH . xxx and ys−1y_{s-1}ys−1​ also have degree ≤1\le 1≤1 in HHH (as λ(x)\lambda(x)λ(x) , resp. λ(ys−1)=λ(yt)\lambda(y_{s-1}) = \lambda(y_t)λ(ys−1​)=λ(yt​) , is missing the…

90. [Edge Colorings] Vizing's proof, Case 2: λ(yt)=c({x,ys})\lambda(y_t) = c(\{x, y_s\})λ(yt​)=c({x,ys​}) ; PPP is a maximal path from yty_tyt​ whose edges are colored λ(x)\lambda(x)λ(x) and λ(yt)\lambda(y_t)λ(yt​) .Subcase: PPP ends at ys−1y_{s-1}ys−1​ . How is GGG colored?

    Swap λ(x)\lambda(x)λ(x) and λ(yt)\lambda(y_t)λ(yt​) on PPP ; recolor {x,yi−1}\{x, y_{i-1}\}{x,yi−1​} with c({x,yi})c(\{x, y_i\})c({x,yi​}) for i=1,…,s−1i = 1, \dots, s - 1i=1,…,s−1 , and color {x,ys−1}\{x, y_{s-1}\}{x,ys−1​} with λ(x)\lambda(x)λ(x) . The last edge of PPP has color λ(x)\lambda(x)λ(x) (as λ(yt)=λ(ys−1)\lambda(y_t) = \lambda(y_{s-1})λ(yt​)=λ(ys−1​) is missing at ys−1y_{s-1}ys−1​ ), so after the swap λ(x)\lambda(x)λ(x) is missing at ys−1y_{s-1}ys−1​ . xxx is not on PPP .

91. [Edge Colorings] Vizing's proof, Case 2: λ(yt)=c({x,ys})\lambda(y_t) = c(\{x, y_s\})λ(yt​)=c({x,ys​}) ; PPP is a maximal path from yty_tyt​ whose edges are colored λ(x)\lambda(x)λ(x) and λ(yt)\lambda(y_t)λ(yt​) .Subcase: PPP ends at xxx . How is GGG colored?

    Swap λ(x)\lambda(x)λ(x) and λ(yt)\lambda(y_t)λ(yt​) on PPP ; recolor {x,yi−1}\{x, y_{i-1}\}{x,yi−1​} with the old c({x,yi})c(\{x, y_i\})c({x,yi​}) for i=1,…,si = 1, \dots, si=1,…,s . The last edge of PPP is {ys,x}\{y_s, x\}{ys​,x} , which becomes λ(x)\lambda(x)λ(x) . So λ(yt)\lambda(y_t)λ(yt​) becomes free at xxx and can go to {x,ys−1}\{x, y_{s-1}\}{x,ys−1​} .

92. [Edge Colorings] Vizing's proof, Case 2: λ(yt)=c({x,ys})\lambda(y_t) = c(\{x, y_s\})λ(yt​)=c({x,ys​}) ; PPP is a maximal path from yty_tyt​ whose edges are colored λ(x)\lambda(x)λ(x) and λ(yt)\lambda(y_t)λ(yt​) .Subcase: PPP ends neither at xxx nor at ys−1y_{s-1}ys−1​ . How is GGG colored?

    Swap λ(x)\lambda(x)λ(x) and λ(yt)\lambda(y_t)λ(yt​) on PPP ; recolor {x,yi−1}\{x, y_{i-1}\}{x,yi−1​} with c({x,yi})c(\{x, y_i\})c({x,yi​}) for i=1,…,ti = 1, \dots, ti=1,…,t , and color {x,yt}\{x, y_t\}{x,yt​} with λ(x)\lambda(x)λ(x) . After the swap, λ(x)\lambda(x)λ(x) is missing at yty_tyt​ . Neither xxx nor ys−1y_{s-1}ys−1​ is on PPP , so the shift still works.

93. [Edge Colorings] What are graphs of class 1 and of class 2?

    Class 1: χ′(G)=Δ(G)\chi&#x27;(G) = \Delta(G)χ′(G)=Δ(G) . Class 2: χ′(G)=Δ(G)+1\chi&#x27;(G) = \Delta(G) + 1χ′(G)=Δ(G)+1 . By Vizing's Theorem, every graph is in one of the two classes.

94. [Edge Colorings] Kőnig's Theorem (1916). What is χ′(G)\chi&#x27;(G)χ′(G) for a bipartite graph GGG ?

    χ′(G)=Δ(G)\boldsymbol{\chi&#x27;(G) = \Delta(G)}χ′(G)=Δ(G) Bipartite graphs are of class 1.

95. [Edge Colorings] Kőnig: bipartite graphs have χ′(G)=Δ(G)\chi&#x27;(G) = \Delta(G)χ′(G)=Δ(G) , by induction on the number of edges. Remove e={v,w}e = \{v, w\}e={v,w} and take a Δ(G)\Delta(G)Δ(G) -edge coloring ccc of G−eG - eG−e .What does the induction step do?

    Take colors λ(v)\lambda(v)λ(v) , λ(w)\lambda(w)λ(w) missing at vvv , www . If equal, color eee with it. Else take the longest path PPP from vvv in the edges colored λ(v)\lambda(v)λ(v) or λ(w)\lambda(w)λ(w) , swap the two colors on PPP , and color eee with λ(w)\lambda(w)λ(w) . λ(v)\lambda(v)λ(v) , λ(w)\lambda(w)λ(w) exist since vvv and www have at most Δ(G)−1\Delta(G) - 1Δ(G)−1 edges in G−eG - eG−e .

96. [Edge Colorings] Kőnig's proof: GGG bipartite, e={v,w}e = \{v, w\}e={v,w} uncolored, λ(v)≠λ(w)\lambda(v) \ne \lambda(w)λ(v)=λ(w) missing at vvv , www ; PPP is the longest path from vvv with edges alternately colored λ(w)\lambda(w)λ(w) , λ(v)\lambda(v)λ(v) .Why can't PPP end at www ?

    Its last edge would be a λ(v)\lambda(v)λ(v) -edge, so PPP has even length, and PPP plus {v,w}\{v, w\}{v,w} would be an odd cycle in a bipartite graph. So after swapping colors on PPP , λ(w)\lambda(w)λ(w) is missing at both vvv and www .

97. [Edge Colorings] Why are line graphs of bipartite graphs perfect?

    By Kőnig's Theorem: for bipartite HHH , χ(LH)=χ′(H)=Δ(H)=ω(LH)\chi(L_H) = \chi&#x27;(H) = \Delta(H) = \omega(L_H)χ(LH​)=χ′(H)=Δ(H)=ω(LH​) . A clique in LHL_HLH​ is a set of pairwise touching edges, which in a triangle-free graph all share a vertex. Induced subgraphs of LHL_HLH​ are line graphs of subgraphs of HHH , again bipartite.

98. [Edge Colorings] What is χ′(Kn)\chi&#x27;(K_n)χ′(Kn​) for n>1n > 1n>1 ?

    n\boldsymbol{n}n for nnn odd, n−1n - 1n−1 for nnn even, i.e. χ′(Kn)=2⌊n+12⌋−1\chi&#x27;(K_n) = 2\lfloor \frac{n+1}{2} \rfloor - 1χ′(Kn​)=2⌊2n+1​⌋−1 . So KnK_nKn​ is of class 2 for odd nnn , class 1 for even nnn .

99. [Edge Colorings] Why does KnK_nKn​ with nnn odd need nnn colors for an edge coloring?

    Each color class has at most n−12\frac{n-1}{2}2n−1​ edges, so at least (n2)/n−12=n\binom{n}{2} / \frac{n-1}{2} = n(2n​)/2n−1​=n colors are needed. A color class is a matching, and nnn is odd.

100. [Edge Colorings] KnK_nKn​ with nnn odd is edge-colored with nnn colors.Why does each vertex miss exactly one color, with different vertices missing different colors?

     Each vertex has degree n−1n - 1n−1 , and each color class has exactly n−12\frac{n-1}{2}2n−1​ edges, so it misses exactly one vertex. nnn colors, each missing one vertex, and nnn vertices, each missing one color: a bijection.