Ch. 10: Coloring Graphs
From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 10.1. The Four Color Problem 10.2. Vertex Coloring 10.3. Edge Coloring 10.4. Excursion: The Heawood Map Coloring Theorem 10.5. Exploration: Modular Coloring
89 flashcards · Mathematics · by lakesare
Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses
Who first posed the Four Color Problem, and when?
Francis Guthrie, in 1852. He noticed that the counties of England could be colored with four colors so that neighboring counties differ. Through his brother Frederick it reached Augustus De Morgan, who wrote to Hamilton about it on October 23, 1852. The question came from mathematicians, not map-makers.
Neighboring states (sharing a boundary line, not just a point) get different colors. Why do these states need four colors?
Nevada is surrounded by a ring of five states, an odd ring that needs three colors, and Nevada needs a fourth. The ring: Utah, Idaho, Oregon, California, Arizona. Utah and New Mexico share only a point, so they may get the same color.
Who announced a proof of the Four Color Theorem in 1879, and how long was it believed?
Alfred Bray Kempe; it was accepted for 11 years, until Heawood found an error in 1890. Kempe, a barrister who had studied under Cayley, published it in the American Journal of Mathematics.
What is a Kempe chain (for two colors, say red and green)?
A chain of neighboring regions (in a graph: a path) whose colors alternate red, green, red, … Interchanging red and green on all regions reachable from one region by such chains keeps the coloring proper.
All regions of a map except XXX are colored red, blue, green, yellow, and XXX is surrounded by a ring of four regions A,B,C,DA, B, C, DA,B,C,D (in this order) colored red, blue, green, yellow.How does Kempe's argument free a color for XXX ?
If no red–green chain joins AAA to CCC , swap red and green on the chains from AAA : red is free. Otherwise swap blue and yellow on the chains from BBB : blue is free. A red–green chain from AAA to CCC closes up through XXX and separates BBB from DDD , so no blue–yellow chain can join BBB to DDD .
Which case of Kempe's 1879 proof was wrong, and who found the error?
A region surrounded by a ring of five regions; Percy John Heawood gave a counterexample in 1890. Kempe believed the ring-of-four argument also worked with five regions. Tait and Frederick Temple also published incorrect proofs.
What is a reducible configuration (in the Four Color Problem)?
An arrangement of regions that cannot occur in a minimum counterexample: every 4-coloring of the regions outside it extends to the whole map. Reducibility was introduced by George David Birkhoff in 1913.
What is an unavoidable set of configurations, and why does an unavoidable set of reducible configurations prove the Four Color Theorem?
A set such that every map contains at least one of its configurations. A minimum counterexample would contain one of them, but a reducible configuration cannot occur in a minimum counterexample.
Why must every region of a minimum counterexample to the Four Color Theorem be surrounded by at least five regions?
A region surrounded by four or fewer regions is reducible: any 4-coloring of the rest extends to it. With at most three neighbors a color is free; with four, Kempe's chain argument frees one. Every map has a region with at most five neighbors, so Kempe's set was unavoidable; only the five-region case failed.
What does it mean that a configuration is DDD -reducible (Heesch)?
Every 4-coloring of the ring of regions around it extends to a 4-coloring of the whole map. It is algorithmic, so computers checked it from the 1960s (a ring of 14 regions has 199,291 colorings). Shimamoto's "horseshoe" would have proved the conjecture if DDD -reducible, but it was not. Heesch also found a second method, CCC -reducibility.
Who proved the Four Color Theorem, when, and how?
Kenneth Appel and Wolfgang Haken, 1976, with a computer-verified unavoidable set of 1936 reducible configurations. About 1200 hours of computer time on three computers. In 1993 Robertson, Sanders, Seymour and Thomas gave a simpler (still computer-assisted) proof with 633 configurations.
Under which pseudonym did William Tutte celebrate the Appel–Haken proof with a poem, and how did he title it?
Blanche Descartes; title: Some Recent Progress in Combinatorics. Published in the first volume of the Journal of Graph Theory. Tutte's acceptance was a major step in the proof's acceptance, as many mathematicians distrusted a computer proof.
What is the dual of a map?
The graph whose vertices are the regions, two adjacent when the regions are neighbors. The dual of every map is a connected planar graph, and every connected planar graph is the dual of some map. The idea first appeared in Kempe's 1879 paper; the word "graph" had been used by Sylvester a year earlier.
What is a proper coloring (or just coloring) of a graph GGG ?
An assignment of one color to each vertex such that adjacent vertices get different colors. As a function: c:V(G)→Nc : V(G) \to \mathbb{N}c:V(G)→N with uv∈E(G)⇒c(u)≠c(v)uv \in E(G) \Rightarrow c(u) \ne c(v)uv∈E(G)⇒c(u)=c(v) .
What is the chromatic number χ(G)\chi(G)χ(G) ?
The smallest number of colors in a coloring of GGG .
What do kkk -colorable, kkk -chromatic and a minimum coloring mean?
kkk -colorable: χ(G)≤k\chi(G) \le kχ(G)≤k . kkk -chromatic: χ(G)=k\chi(G) = kχ(G)=k . Minimum coloring: a coloring with χ(G)\chi(G)χ(G) colors. GGG is kkk -colorable when it can be colored from a set of kkk colors. A coloring using kkk colors is a kkk -coloring.
The Four Color Theorem (Theorem 10.1), stated for graphs
Every planar graph GGG has χ(G)≤4\chi(G) \le 4χ(G)≤4 . Coloring the regions of a map is coloring the vertices of its dual, a planar graph.
The Problem of the Five Princes (Möbius, 1840): divide a kingdom into five regions so that each region shares a boundary with the other four. Why is it impossible?
Its dual would be K5K_5K5 , which is not planar. Tietze's Problem of the Five Palaces (join every two of five palaces by noncrossing roads) asks for a plane drawing of K5K_5K5 directly.
No map has five regions every two of which are neighbors. Why doesn't that prove the Four Color Theorem?
A map might need five colors without containing five mutually neighboring regions. In graph terms: χ(G)\chi(G)χ(G) can exceed the largest kkk with Kk⊆GK_k \subseteq GKk⊆G .
When is χ(G)=1\chi(G) = 1χ(G)=1 ?
Exactly when GGG has no edges, i.e. G=Kn‾G = \overline{K_n}G=Kn . One edge already needs two colors.
What is the independence number α(G)\alpha(G)α(G) ?
The largest number of vertices in an independent set (a set of pairwise nonadjacent vertices). An independent set of that size is a maximum independent set. For C6C_6C6 : {v2,v4,v6}\{v_2, v_4, v_6\}{v2,v4,v6} , so α(C6)=3\alpha(C_6) = 3α(C6)=3 .
GGG is kkk -chromatic. What does that say about partitioning V(G)V(G)V(G) into independent sets?
V(G)V(G)V(G) can be partitioned into kkk independent sets, but not into k−1k - 1k−1 . The parts are the color classes. So χ(G)\chi(G)χ(G) is the smallest number of independent sets partitioning V(G)V(G)V(G) .
Theorem 10.2. When does a graph GGG have χ(G)=2\chi(G) = 2χ(G)=2 ?
Exactly when GGG is a nonempty bipartite graph. Two color classes V1,V2V_1, V_2V1,V2 are independent, so every edge joins V1V_1V1 to V2V_2V2 . Nonempty: GGG has an edge.
What is χ(Cn)\chi(C_n)χ(Cn) for n≥3n \ge 3n≥3 ?
2 if nnn is even, 3 if nnn is odd. An odd cycle isn't bipartite, so needs 3; color one vertex 3 and alternate 1, 2 on the rest.
To prove χ(G)=k\chi(G) = kχ(G)=k , which two things must you show?
(1) GGG has no (k−1)(k-1)(k−1) -coloring, and (2) GGG has a kkk -coloring. e.g. a triangle in GGG gives (1) for k=3k = 3k=3 .
Coloring this graph's 5-cycle (black vertices) first and extending it with colors 1, 2, 3 forces two adjacent vertices colored 3. Does χ(G)=4\chi(G) = 4χ(G)=4 follow?
No. One failed attempt says nothing; this graph has a 3-coloring. χ(G)=3\chi(G) = 3χ(G)=3 : it contains a triangle, and here is a 3-coloring.
Classes must be scheduled so that two classes sharing a student meet at different times. How does graph theory give the fewest time periods?
It is χ(H)\chi(H)χ(H) , where HHH has the classes as vertices, two joined when some student takes both. A color class is a set of classes that can share a period.
A graph contains an odd cycle and a vertex adjacent to every vertex of that cycle. What lower bound on χ\chiχ follows?
χ≥4\boldsymbol{\chi \ge 4}χ≥4 The odd cycle needs 3 colors, and the extra vertex differs from all of them. Six summer classes: the 5-cycle GT, S, AC, G, MA plus LA give 4 periods; this 4-coloring achieves it.
For a graph GGG of order nnn , when is χ(G)=n\chi(G) = nχ(G)=n ?
Exactly when G=KnG = K_nG=Kn . Otherwise two nonadjacent vertices u,vu, vu,v can share color 1 and the other n−2n - 2n−2 vertices get 2,…,n−12, \dots, n - 12,…,n−1 .
HHH is a subgraph of GGG . How do χ(H)\chi(H)χ(H) and χ(G)\chi(G)χ(G) compare?
χ(H)≤χ(G)\boldsymbol{\chi(H) \le \chi(G)}χ(H)≤χ(G) Every coloring of GGG restricts to a coloring of HHH .
A complete subgraph of a graph is a clique.
The order of a largest clique is the clique number ω(G)\omega(G)ω(G) . Also α(G)=k\alpha(G) = kα(G)=k if and only if ω(G‾)=k\omega(\overline{G}) = kω(G)=k .
Theorem 10.5. GGG has order nnn , clique number ω(G)\omega(G)ω(G) (largest clique) and independence number α(G)\alpha(G)α(G) (largest independent set). χ(G)≥ ?\chi(G) \ge \; ?χ(G)≥? and χ(G)≥ ?\chi(G) \ge \; ?χ(G)≥?
χ(G)≥ω(G)\boldsymbol{\chi(G) \ge \omega(G)}χ(G)≥ω(G) and χ(G)≥nα(G)\boldsymbol{\chi(G) \ge \frac{n}{\alpha(G)}}χ(G)≥α(G)n A clique of order ω(G)\omega(G)ω(G) needs ω(G)\omega(G)ω(G) colors. And the χ(G)\chi(G)χ(G) color classes each have at most α(G)\alpha(G)α(G) vertices, so n≤χ(G) α(G)n \le \chi(G)\,\alpha(G)n≤χ(G)α(G) .
Which graph shows that both bounds χ(G)≥ω(G)\chi(G) \ge \omega(G)χ(G)≥ω(G) and χ(G)≥n/α(G)\chi(G) \ge n / \alpha(G)χ(G)≥n/α(G) can be attained at once?
K3,3,3,3K_{3,3,3,3}K3,3,3,3 (complete 4-partite, parts of size 3): χ=ω=4=12/3=n/α\chi = \omega = 4 = 12/3 = n/\alphaχ=ω=4=12/3=n/α . Color part ViV_iVi with color iii .
Cars from traffic lanes may enter an intersection together during a light phase only if they can't collide. How do you find the fewest phases?
χ(G)\chi(G)χ(G) , where the lanes are vertices, joined when their cars could collide. Here L2,L4,L6,L8L2, L4, L6, L8L2,L4,L6,L8 pairwise conflict ( K4K_4K4 ), and a 4-coloring exists: 4 phases. A partition into 4 independent sets alone only shows χ(G)≤4\chi(G) \le 4χ(G)≤4 .
Theorem 10.7. Upper bound on χ(G)\chi(G)χ(G) in terms of the maximum degree Δ(G)\Delta(G)Δ(G) ?
χ(G)≤1+Δ(G)\boldsymbol{\chi(G) \le 1 + \Delta(G)}χ(G)≤1+Δ(G) Equality for odd cycles and complete graphs.
Why does every graph GGG satisfy χ(G)≤1+Δ(G)\chi(G) \le 1 + \Delta(G)χ(G)≤1+Δ(G) ?
Greedy coloring: color v1,v2,…v_1, v_2, \dotsv1,v2,… in turn, each with the smallest color not on its already colored neighbors. A vertex vvv has only degv≤Δ(G)\deg v \le \Delta(G)degv≤Δ(G) neighbors, so one of 1,…,1+degv1, \dots, 1 + \deg v1,…,1+degv is free.
Brooks' Theorem. For which connected graphs GGG does χ(G)≤Δ(G)\chi(G) \le \Delta(G)χ(G)≤Δ(G) hold?
All except odd cycles and complete graphs. Those two are exactly the connected graphs with χ(G)=1+Δ(G)\chi(G) = 1 + \Delta(G)χ(G)=1+Δ(G) .
Theorem 10.9. Upper bound on χ(G)\chi(G)χ(G) in terms of minimum degrees δ(H)\delta(H)δ(H) of subgraphs?
χ(G)≤1+maxδ(H)\boldsymbol{\chi(G) \le 1 + \max \delta(H)}χ(G)≤1+maxδ(H) , the maximum over all induced subgraphs HHH of GGG . Never worse than 1+Δ(G)1 + \Delta(G)1+Δ(G) , and often better, since δ(H)≤Δ(G)\delta(H) \le \Delta(G)δ(H)≤Δ(G) .
kkk is the maximum of δ(H)\delta(H)δ(H) over all induced subgraphs HHH of a graph GGG of order nnn ; the claim is χ(G)≤1+k\chi(G) \le 1 + kχ(G)≤1+k .In which order does the proof color the vertices greedily, and why does that work?
Pick vnv_nvn of minimum degree in GGG , then vn−1v_{n-1}vn−1 of minimum degree in G−vnG - v_nG−vn , and so on; color v1,v2,…,vnv_1, v_2, \dots, v_nv1,v2,…,vn . viv_ivi has minimum degree in the induced subgraph on v1,…,viv_1, \dots, v_iv1,…,vi , which is at most kkk ; so at most kkk neighbors are colored before it, and one of 1,…,k+11, \dots, k + 11,…,k+1 is free.
What is the shadow graph S(G)S(G)S(G) of a graph GGG ?
Add, for each vertex vvv of GGG , a new shadow vertex v′v'v′ joined to the neighbors of vvv . vvv and v′v'v′ are not adjacent, and no two shadow vertices are adjacent.
What is the Grötzsch graph, and what makes it notable?
S(C5)S(C_5)S(C5) plus a vertex zzz joined to the five shadow vertices; it is triangle-free with χ=4\chi = 4χ=4 . S(C5)S(C_5)S(C5) is the shadow graph of C5C_5C5 (each vertex vvv gets a copy v′v'v′ joined to the neighbors of vvv ).
Give two graphs with χ(G)>ω(G)\chi(G) > \omega(G)χ(G)>ω(G) (chromatic number above clique number).
C5C_5C5 ( χ=3\chi = 3χ=3 , ω=2\omega = 2ω=2 ) and the Grötzsch graph ( χ=4\chi = 4χ=4 , ω=2\omega = 2ω=2 ).
Theorem 10.10. For which kkk is there a triangle-free graph with chromatic number kkk ?
Every k≥3k \ge 3k≥3 . So large chromatic number doesn't need large cliques. The proof is due to Jan Mycielski.
How does Mycielski's proof build a triangle-free kkk -chromatic graph GGG from a triangle-free (k−1)(k-1)(k−1) -chromatic graph FFF ?
GGG = the shadow graph S(F)S(F)S(F) plus a new vertex zzz joined to all shadow vertices. Shadow vertex x′x'x′ is joined to the neighbors of xxx . A kkk -coloring: give x′x'x′ the color of xxx and zzz a new color kkk . Starting from C5C_5C5 this gives the Grötzsch graph.
FFF is triangle-free; GGG is FFF plus a shadow vertex x′x'x′ for each x∈V(F)x \in V(F)x∈V(F) , joined to the neighbors of xxx , plus a vertex zzz joined to all shadow vertices.Why is GGG triangle-free?
A triangle would be u,v,w′u, v, w'u,v,w′ with uv∈E(F)uv \in E(F)uv∈E(F) , but then www is adjacent to uuu and vvv : a triangle in FFF . No two shadow vertices are adjacent, so a triangle has at most one shadow vertex. zzz is adjacent only to shadow vertices, so the triangle avoids zzz . FFF has no triangle, so exactly one vertex is a shadow vertex.
FFF is triangle-free with χ(F)=k−1\chi(F) = k - 1χ(F)=k−1 ; GGG is FFF plus a shadow vertex x′x'x′ for each x∈V(F)x \in V(F)x∈V(F) , joined to the neighbors of xxx , plus a vertex zzz joined to all shadow vertices.Why has GGG no (k−1)(k-1)(k−1) -coloring?
Recolor each y∈V(F)y \in V(F)y∈V(F) that has the color of zzz with the color of y′y'y′ : this gives a (k−2)(k-2)(k−2) -coloring of FFF , a contradiction. Say c(z)=k−1c(z) = k - 1c(z)=k−1 . No shadow vertex has color k−1k - 1k−1 , since zzz is adjacent to all of them. c(y′)c(y')c(y′) differs from the colors of the neighbors of yyy , since y′y'y′ is adjacent to them, and the recolored vertices are pairwise nonadjacent.
A graph GGG with χ(H)=ω(H)\chi(H) = \omega(H)χ(H)=ω(H) for every induced subgraph HHH of GGG is called perfect.
Introduced by Claude Berge in 1963. Every bipartite and every complete multipartite graph is perfect.
What does the Perfect Graph Theorem say?
A graph is perfect if and only if its complement is perfect. Conjectured by Berge, proved by László Lovász in 1972.
What does the Strong Perfect Graph Theorem say?
GGG is perfect if and only if neither GGG nor G‾\overline{G}G contains an induced odd cycle of length 5 or more. Conjectured by Berge, proved in 2002 by Chudnovsky, Robertson, Seymour and Thomas.
What is an edge coloring of a nonempty graph, and what is the chromatic index χ′(G)\chi'(G)χ′(G) ?
An assignment of colors to the edges with adjacent edges colored differently; χ′(G)\chi'(G)χ′(G) is the fewest colors possible. Also called the edge chromatic number. An edge coloring with kkk colors is a kkk -edge coloring.
Why is χ′(G)≥Δ(G)\chi'(G) \ge \Delta(G)χ′(G)≥Δ(G) for every nonempty graph GGG ?
The Δ(G)\Delta(G)Δ(G) edges at a vertex of maximum degree are pairwise adjacent, so they need distinct colors.
Δ(G)=3\Delta(G) = 3Δ(G)=3 and this is a 4-edge coloring. Why has GGG no 3-edge coloring?
The degree-3 vertices force xyxyxy and yzyzyz to have the same color, though they are adjacent. Say uv=1uv = 1uv=1 , ux=2ux = 2ux=2 , uz=3uz = 3uz=3 . Then vx=3vx = 3vx=3 , vz=2vz = 2vz=2 (each vertex of degree 3 sees all three colors), so xy=1xy = 1xy=1 and yz=1yz = 1yz=1 . Hence χ′(G)=4\chi'(G) = 4χ′(G)=4 .
Vizing's Theorem. For every nonempty graph GGG , ?≤χ′(G)≤ ?\; ? \le \chi'(G) \le \; ??≤χ′(G)≤?
Δ(G)≤χ′(G)≤1+Δ(G)\boldsymbol{\Delta(G) \le \chi'(G) \le 1 + \Delta(G)}Δ(G)≤χ′(G)≤1+Δ(G) So knowing the maximum degree nearly determines the chromatic index.
What happened when Vadim Vizing submitted his theorem on edge colorings to the journal Doklady?
It was rejected as uninteresting. It appeared in 1964 in a local Novosibirsk journal, Metody Diskretnogo Analiza, and was already well known by then through Zykov.
What is χ′(Cn)\chi'(C_n)χ′(Cn) for n≥3n \ge 3n≥3 ?
2 if nnn is even, 3 if nnn is odd. Alternating colors 1, 2 around an odd cycle gives the last edge the same color as the first, which is adjacent to it.
In an edge coloring of a graph of order nnn , how many edges can have the same color at most?
⌊n/2⌋\boldsymbol{\lfloor n/2 \rfloor}⌊n/2⌋ , i.e. n−12\frac{n-1}{2}2n−1 when nnn is odd. Edges of one color are pairwise nonadjacent, so each vertex lies on at most one of them.
Theorem 10.13. GGG has odd order nnn and size mmm . Which condition on mmm forces χ′(G)=1+Δ(G)\chi'(G) = 1 + \Delta(G)χ′(G)=1+Δ(G) ?
m>(n−1)Δ(G)2\boldsymbol{m > \frac{(n-1)\Delta(G)}{2}}m>2(n−1)Δ(G) Δ(G)\Delta(G)Δ(G) colors cover at most Δ(G)⋅n−12\Delta(G) \cdot \frac{n-1}{2}Δ(G)⋅2n−1 edges, so χ′(G)>Δ(G)\chi'(G) > \Delta(G)χ′(G)>Δ(G) ; Vizing gives ≤1+Δ(G)\le 1 + \Delta(G)≤1+Δ(G) .
Finding χ′(G)\chi'(G)χ′(G) is the same as partitioning E(G)E(G)E(G) into as few as possible … ?
Matchings (independent sets of edges), i.e. decomposing GGG into 1-regular subgraphs. If those subgraphs are spanning, they form a 1-factorization of GGG .
For an rrr -regular graph GGG ( r≥1r \ge 1r≥1 ), when is χ′(G)=r\chi'(G) = rχ′(G)=r ?
Exactly when GGG is 1-factorable. Each of the rrr color classes must then cover every vertex, i.e. be a 1-factor. Otherwise χ′(G)=r+1\chi'(G) = r + 1χ′(G)=r+1 by Vizing's Theorem.
Alvin invites three married couples: Bob and Carrie, David and Edith, Frank and Gena. Each guest plays tennis against every other guest except their spouse, and Alvin plays David, Edith, Frank and Gena. Nobody plays twice a day. How many days are needed?
6 days. The graph HHH of matches has order n=7n = 7n=7 , size m=16m = 16m=16 , Δ(H)=5\Delta(H) = 5Δ(H)=5 . Since 16>(7−1)⋅52=1516 > \frac{(7-1) \cdot 5}{2} = 1516>2(7−1)⋅5=15 and nnn is odd, χ′(H)=1+Δ(H)=6\chi'(H) = 1 + \Delta(H) = 6χ′(H)=1+Δ(H)=6 .
Theorem 10.15. What is χ′(Kn)\chi'(K_n)χ′(Kn) for n≥2n \ge 2n≥2 ?
n\boldsymbol{n}n if nnn is odd, n−1\boldsymbol{n - 1}n−1 if nnn is even. KnK_nKn is (n−1)(n-1)(n−1) -regular, and it is 1-factorable exactly when nnn is even. χ′(K4)=3\chi'(K_4) = 3χ′(K4)=3 .
Five players form 2-person bridge teams. Every team plays every team with no player in common, and no team plays twice a day. Which graph models this, and how many days are needed?
The Petersen graph (teams as vertices, games as edges); 4 days. It is 3-regular but not 1-factorable, so χ′(G)=4\chi'(G) = 4χ′(G)=4 .
König's Theorem (Theorem 10.17). What is χ′(G)\chi'(G)χ′(G) for a nonempty bipartite graph GGG ?
χ′(G)=Δ(G)\boldsymbol{\chi'(G) = \Delta(G)}χ′(G)=Δ(G) e.g. even cycles have chromatic index 2.
König: a nonempty bipartite graph GGG with Δ(G)=r\Delta(G) = rΔ(G)=r has χ′(G)=r\chi'(G) = rχ′(G)=r . (Every rrr -regular bipartite graph, r≥1r \ge 1r≥1 , is 1-factorable.)How does the proof get an rrr -edge coloring of GGG ?
Embed GGG in an rrr -regular bipartite graph HHH ; the rrr 1-factors of HHH , restricted to GGG , are the color classes. Build HHH : take a copy G′G'G′ with its partite sets swapped and join each vertex of degree <r< r<r to its copy. This raises δ\deltaδ by 1 and stays bipartite; repeat r−δ(G)r - \delta(G)r−δ(G) times.
What is a cubic map?
A connected, 3-regular, bridgeless plane graph.
Why did Tait need to 4-color only the regions of cubic maps?
Replace each vertex of degree 4 or more by a small circle: the result is a cubic map, and a 4-coloring of its regions gives one of the original map. Shrinking the circle back gives each region its color.
Theorem 10.18 (Tait). When can the regions of a cubic map GGG be colored with four colors?
Exactly when χ′(G)=3\chi'(G) = 3χ′(G)=3 .
A 3-edge coloring of a 3-regular graph is called a Tait coloring.
Why is every Hamiltonian 3-regular graph 3-edge colorable?
Color the Hamiltonian cycle alternately red and blue; the remaining edges form a 1-factor, colored green. A 3-regular graph has even order, so the alternation closes up.
Tait reduced the Four Color Theorem to 3-edge coloring 3-connected 3-regular planar graphs. Which false belief made him think he had a proof?
That every 3-connected 3-regular planar graph is Hamiltonian. Tutte refuted it in 1946 with the Tutte graph:
Was Heawood's 1890 example a counterexample to the Four Color Conjecture?
No, only to Kempe's proof. The map is easily 4-colored. Heawood adapted Kempe's technique to prove that every map is 5-colorable.
The Five Color Theorem (Theorem 10.19)
Every planar graph is 5-colorable. Proved by Heawood in 1890 with Kempe chains.
Proof of the Five Color Theorem: let GGG be a planar graph of smallest order that is not 5-colorable.Why may we assume a vertex vvv of degree 5 whose neighbors use all five colors?
Every planar graph has a vertex vvv of degree ≤5\le 5≤5 , and G−vG - vG−v is 5-colorable; if vvv had fewer than five neighbor colors, a color would be free for vvv .
In the Five Color Theorem proof, G−vG - vG−v is 5-colored, and the neighbors v1,…,v5v_1, \dots, v_5v1,…,v5 of vvv (in clockwise order) are green, red, yellow, purple, blue. How is a color freed for vvv if G−vG - vG−v has no red–blue path from v2v_2v2 to v5v_5v5 ?
Swap red and blue on all vertices joined to v5v_5v5 by red–blue paths: v5v_5v5 turns red, v2v_2v2 stays red, so blue is free for vvv .
In the Five Color Theorem proof, G−vG - vG−v is 5-colored, and the neighbors v1,…,v5v_1, \dots, v_5v1,…,v5 of vvv (in clockwise order) are green, red, yellow, purple, blue.What if G−vG - vG−v has a red–blue path from v2v_2v2 to v5v_5v5 ?
Then no green–yellow path joins v1v_1v1 to v3v_3v3 , so swapping green and yellow from v1v_1v1 frees green. The red–blue path together with vvv forms a cycle in the plane that separates v1v_1v1 from v3v_3v3 .
What is χ(Sk)\chi(S_k)χ(Sk) , for the surface SkS_kSk of genus kkk (a sphere with kkk handles)?
The largest chromatic number of a graph that can be embedded on SkS_kSk . χ(S0)=4\chi(S_0) = 4χ(S0)=4 is the Four Color Theorem; between 1890 and 1976 it was only known that χ(S0)\chi(S_0)χ(S0) is 4 or 5.
Theorem 10.20 (Heawood). For every positive integer kkk , χ(Sk)≤ ?\chi(S_k) \le \; ?χ(Sk)≤? ( SkS_kSk is the surface of genus kkk .)
χ(Sk)≤7+1+48k2\boldsymbol{\chi(S_k) \le \dfrac{7 + \sqrt{1 + 48k}}{2}}χ(Sk)≤27+1+48k For the torus ( k=1k = 1k=1 ): χ(S1)≤7\chi(S_1) \le 7χ(S1)≤7 .
Claim: every graph GGG embeddable on SkS_kSk ( k≥1k \ge 1k≥1 ) has χ(G)≤h=7+1+48k2\chi(G) \le h = \frac{7 + \sqrt{1 + 48k}}{2}χ(G)≤h=27+1+48k . Note h−1=6+12(k−1)hh - 1 = 6 + \frac{12(k-1)}{h}h−1=6+h12(k−1) .What is the key idea of the proof?
χ(G)≤1+δ(H)\chi(G) \le 1 + \delta(H)χ(G)≤1+δ(H) for an induced subgraph HHH of largest minimum degree, and the genus bound forces δ(H)≤h−1\delta(H) \le h - 1δ(H)≤h−1 . If HHH has order n≤hn \le hn≤h , then χ(G)≤n≤h\chi(G) \le n \le hχ(G)≤n≤h . Otherwise, with mmm edges, γ(H)≥m6−n2+1\gamma(H) \ge \frac{m}{6} - \frac{n}{2} + 1γ(H)≥6m−2n+1 gives m≤3n+6(k−1)m \le 3n + 6(k-1)m≤3n+6(k−1) , so n δ(H)≤2mn\,\delta(H) \le 2mnδ(H)≤2m yields δ(H)≤6+12(k−1)n≤6+12(k−1)h=h−1\delta(H) \le 6 + \frac{12(k-1)}{…
What is χ(S1)\chi(S_1)χ(S1) , the largest chromatic number of a graph on the torus, and which graph attains it?
7\boldsymbol{7}7 , attained by K7K_7K7 , which embeds on the torus. Opposite sides of the rectangle are identified.
The Heawood Map Coloring Theorem (Theorem 10.21). For every positive integer kkk , χ(Sk)= ?\chi(S_k) = \; ?χ(Sk)=?
χ(Sk)=⌊7+1+48k2⌋\boldsymbol{\chi(S_k) = \left\lfloor \dfrac{7 + \sqrt{1 + 48k}}{2} \right\rfloor}χ(Sk)=⌊27+1+48k⌋ Heawood proved ≤\le≤ ; the full proof came 78 years later, chiefly by Gerhard Ringel and Ted Youngs. With the Four Color Theorem it holds for k=0k = 0k=0 too (value 4).
Known: χ(Sk)≤⌊7+1+48k2⌋=n\chi(S_k) \le \left\lfloor \frac{7 + \sqrt{1 + 48k}}{2} \right\rfloor = nχ(Sk)≤⌊27+1+48k⌋=n , and γ(Kn)=⌈(n−3)(n−4)12⌉\gamma(K_n) = \left\lceil \frac{(n-3)(n-4)}{12} \right\rceilγ(Kn)=⌈12(n−3)(n−4)⌉ ( γ\gammaγ = genus).How does the proof of equality show that some graph on SkS_kSk has chromatic number nnn ?
KnK_nKn embeds on SkS_kSk : 2n−7≤1+48k2n - 7 \le \sqrt{1 + 48k}2n−7≤1+48k gives k≥(n−3)(n−4)12k \ge \frac{(n-3)(n-4)}{12}k≥12(n−3)(n−4) , so γ(Kn)≤k\gamma(K_n) \le kγ(Kn)≤k . And χ(Kn)=n\chi(K_n) = nχ(Kn)=n . So the hard part was the genus formula for KnK_nKn .
c:V(G)→Zkc : V(G) \to \mathbb{Z}_kc:V(G)→Zk is a vertex coloring in which adjacent vertices may share a color. What is the color sum σ(v)\sigma(v)σ(v) ?
σ(v)=∑u∈N(v)c(u)\boldsymbol{\sigma(v) = \sum_{u \in N(v)} c(u)}σ(v)=∑u∈N(v)c(u) , computed in Zk\mathbb{Z}_kZk (the sum of the colors of the neighbors of vvv ).
What is a modular kkk -coloring of a nontrivial connected graph GGG , and what is mc(G)\operatorname{mc}(G)mc(G) ?
A coloring c:V(G)→Zkc : V(G) \to \mathbb{Z}_kc:V(G)→Zk in which adjacent vertices have different color sums; mc(G)\operatorname{mc}(G)mc(G) is the least such kkk . σ(v)\sigma(v)σ(v) is the sum in Zk\mathbb{Z}_kZk of the colors of the neighbors of vvv ; adjacent vertices may share a color. Modular chromatic number mc(P4×P2)=2\operatorname{mc}(P_4 \times P_2) = 2mc(P4×P2)=2 (colors in the circles, sums beside them):
A modular kkk -coloring of a nontrivial connected graph is a c:V(G)→Zkc : V(G) \to \mathbb{Z}_kc:V(G)→Zk such that adjacent vertices have different color sums σ(v)=∑u∈N(v)c(u)\sigma(v) = \sum_{u \in N(v)} c(u)σ(v)=∑u∈N(v)c(u) .Why does every nontrivial connected graph with vertices v1,…,vnv_1, \dots, v_nv1,…,vn have one?
Take c(vi)=2i−1c(v_i) = 2^{i-1}c(vi)=2i−1 and k=2n−2k = 2^n - 2k=2n−2 . Each σ(vi)\sigma(v_i)σ(vi) is an integer from 1 to kkk . For adjacent vi,vjv_i, v_jvi,vj , the binary expansion of σ(vi)\sigma(v_i)σ(vi) contains 2j−12^{j-1}2j−1 but that of σ(vj)\sigma(v_j)σ(vj) does not.
How do χ(G)\chi(G)χ(G) and mc(G)\operatorname{mc}(G)mc(G) (the modular chromatic number) compare?
χ(G)≤mc(G)\boldsymbol{\chi(G) \le \operatorname{mc}(G)}χ(G)≤mc(G) In a modular kkk -coloring, the color sums σ(v)∈Zk\sigma(v) \in \mathbb{Z}_kσ(v)∈Zk give adjacent vertices different values: a proper kkk -coloring.
Does every connected bipartite graph have modular chromatic number 2?
No. This bipartite graph has mc(G)=3\operatorname{mc}(G) = 3mc(G)=3 : Colors in Z3\mathbb{Z}_3Z3 in the circles, color sums beside them. Every nontrivial path has mc=2\operatorname{mc} = 2mc=2 .
Why has this tree TTT no modular 2-coloring?
The sums would alternate 0, 1 along TTT ; then σ(w2)=σ(v8)=1\sigma(w_2) = \sigma(v_8) = 1σ(w2)=σ(v8)=1 forces c(v5)=c(v7)=1c(v_5) = c(v_7) = 1c(v5)=c(v7)=1 , so σ(v6)=0\sigma(v_6) = 0σ(v6)=0 , not 1. Adjacent vertices have different sums in Z2\mathbb{Z}_2Z2 , so the sums form the unique 2-coloring of TTT (up to symmetry). mc(T)=3\operatorname{mc}(T) = 3mc(T)=3 :
Theorem 10.25. What values can mc(T)\operatorname{mc}(T)mc(T) (modular chromatic number) take for a nontrivial tree TTT ?
2 or 3.
Theorem 10.26. What is mc(Cn)\operatorname{mc}(C_n)mc(Cn) (modular chromatic number) for n≥3n \ge 3n≥3 ?
2 if n≡0(mod4)n \equiv 0 \pmod 4n≡0(mod4) , and 3 otherwise. So even cycles like C6C_6C6 have mc=3\operatorname{mc} = 3mc=3 although χ=2\chi = 2χ=2 .