Day 67 — Coloring & planarity

Day 67 — Coloring & planarity

Stage VI · concept day
Goal: Define vertex coloring and chromatic number; use clique lower bounds; bipartite \(\chi=2\); state the four color theorem; Kuratowski/Wagner awareness; dual graphs lite; register allocation story.

Why this matters

Coloring models conflict-free assignment: exams, frequencies, registers, schedule slots. Planarity models chip layout and map drawing without crossings. The four color theorem is a landmark; register allocation is the killer CS application of coloring ideas (heuristics in practice).

Theory

Vertex coloring

A proper \(k\)-coloring of \(G\) assigns each vertex a color in \(\{1,\ldots,k\}\) so adjacent vertices get different colors.
Chromatic number \(\chi(G)\) = minimum \(k\) such that a proper \(k\)-coloring exists.

Independent set: no two adjacent—each color class is an independent set. Coloring = partition into independent sets.

Easy bounds

• \(\chi(G)\le \Delta(G)+1\) (greedy coloring; Brooks’ theorem improves to \(\Delta\) except complete and odd cycles).
  
• \(\chi(G)\ge \omega(G)\) where \(\omega(G)\) is the clique number (size of largest clique)—all clique vertices need distinct colors.
  
• \(\chi(G)\ge n/\alpha(G)\) where \(\alpha\) is independence number (awareness).

Special values

Graph	\(\chi\)
Empty \(E_n\)	1
Bipartite, edges >0	2
Odd cycle \(C_{2k+1}\)	3
Even cycle	2
\(K_n\)	\(n\)
Tree \(n\ge 2\)	2

Theorem. \(G\) bipartite ⇔ \(\chi(G)\le 2\) (for graphs with at least one edge: \(=2\)).

Greedy coloring

Order vertices \(v_1,\ldots,v_n\); assign to each the smallest color not used by earlier neighbors.
Uses at most \(\Delta+1\) colors. Order matters for the number used (not always \(\chi\)).

Mycielski / high \(\chi\) triangle-free (awareness)

\(\chi\) can be arbitrarily large even with \(\omega=2\) (no triangles)—clique bound can be weak.

Planar graphs

\(G\) is planar if it can be drawn in the plane with no edge crossings (except at vertices).
Plane graph: a specific planar embedding.

Euler’s formula (connected plane graph): \(n-m+f=2\) where \(f\) is faces (including outer face).

Consequences for simple planar: \(m\le 3n-6\) for \(n\ge 3\); \(m\le 2n-4\) if triangle-free.
⇒ \(K_5\) nonplanar (\(10>9\)); \(K_{3,3}\) nonplanar (\(9>8\) for bipartite bound).

Four color theorem

Theorem (Appel–Haken 1976, computer-assisted; later simplifications). Every planar graph is 4-colorable: \(\chi(G)\le 4\) if \(G\) planar.

Five color theorem has a shorter classical proof.
Three color planar is NP-hard to decide in general.

Kuratowski / Wagner (awareness)

\(G\) planar ⇔ no subdivision of \(K_5\) or \(K_{3,3}\) (Kuratowski) ⇔ no \(K_5\) or \(K_{3,3}\) minor (Wagner).
Use: exhibit a \(K_{3,3}\) or \(K_5\) subdivision to prove nonplanar.

Dual graphs (lite)

For a plane graph, dual \(G^*\): face → vertex; edge between faces → edge in dual.
Face coloring of \(G\) ↔︎ vertex coloring of \(G^*\). Map coloring reduces to planar dual coloring.

Register allocation (story)

Compiler: variables/live ranges → vertices; edge if live ranges overlap (interfere).
Proper coloring → assign registers (colors) so interfering variables differ.
If \(\chi>\) number of registers, spill to memory (add vertices/edges heuristics).
Interference graphs are not always perfect/easy; SSA form helps structure.
Moral: graph coloring is the right model; exact \(\chi\) hard ⇒ heuristics (chordal graphs nice when SSA).

Greedy bound proof

Theorem. \(\chi(G)\le \Delta(G)+1\).
Proof. Order vertices arbitrarily. When coloring \(v\), it has at most \(\Delta\) neighbors, hence at most \(\Delta\) forbidden colors among those already colored; among \(\Delta+1\) colors, one remains free. \(\square\)

Brooks’ theorem (stated only): if \(G\) is connected, not complete, and not an odd cycle, then \(\chi\le \Delta\).

Euler ⇒ sparse ⇒ colorable (planar)

From \(m\le 3n-6\) (\(n\ge 3\) simple planar), average degree \(\frac{2m}{n}<6\), so \(\delta\le 5\). Every simple planar graph is \(5\)-degenerate ⇒ greedy coloring in a degeneracy order uses ≤6 colors. Five- and four-color theorems improve this; the edge bound is the engine of elementary planar coloring arguments.

Clique vs chromatic gap

\(\omega\le\chi\) always, but \(\chi-\omega\) can be large (Mycielski construction awareness). Odd cycles: \(\omega=2\), \(\chi=3\). Never assume equality outside perfect graphs (culture word).

Worked examples

Example 1 — \(\chi(K_4)=4\)

Planar (\(K_4\) planar!); needs 4 colors. So 4-color bound tight among planar graphs.

Example 2 — \(\chi(C_5)=3\)

Odd cycle; \(\omega=2<\chi\).

Example 3 — Bipartite

\(K_{2,3}\): \(\chi=2\); \(\omega=2\).

Example 4 — Greedy

Path \(a{-}b{-}c\): order \(a,c,b\) may use 2 colors; always ≤ \(\Delta+1=3\).

Example 5 — Clique bound

Any graph containing \(K_4\) has \(\chi\ge 4\).

Example 6 — \(K_5\) nonplanar

\(m=10>3\cdot5-6=9\).

Example 7 — \(K_{3,3}\) nonplanar

Bipartite planar \(m\le 2n-4=8\) but \(m=9\).

Example 8 — Planar max edges

Maximal planar triangulations: \(m=3n-6\), all faces triangles (n≥3).

Example 9 — Dual of tetrahedron

\(K_4\) plane embedding dual related to itself culture.

Example 10 — Register story micro

Variables \(a,b,c\): \(a\) overlaps \(b\), \(b\) overlaps \(c\), \(a\) not with \(c\): path interference ⇒ \(\chi=2\) registers enough.

Example 11 — Three mutual overlap

\(K_3\) interference ⇒ 3 registers.

Example 12 — Brooks

Connected \(\Delta=3\) not \(K_4\) not odd cycle ⇒ \(\chi\le 3\).

Example 13 — Map

Four countries all mutually adjacent impossible on plane without enclave tricks—related to \(K_5\) nonplanar.

Example 14 — \(\chi\) upper by degeneracy

Planar graphs are 5-degenerate ⇒ greedy ≤6; better theorems give 5, then 4.

Example 15 — Interval graphs

Interval/live-range pure interval graphs are perfect chordal—\(\chi=\omega\) poly-time—why register allocation on intervals is easier.

Example 16 — Greedy order matters

Bipartite \(K_{2,2}=C_4\) has \(\chi=2\), \(\Delta=2\). A bad ordering can still use only ≤3 colors by the theorem; on bipartite graphs some orders use exactly 2. Point: greedy number depends on order; \(\chi\) does not.

Example 17 — Exam schedule

Courses \(\{A,B,C,D\}\); conflicts \(AB,BC,CD,DA\) (a \(C_4\)): \(\chi=2\)—two slots suffice (schedule opposite courses together). Add diagonal \(AC\): now \(K_3\) plus, \(\chi=3\).

Example 18 — Euler check plane tree

Tree \(n\) vertices, \(m=n-1\), one face unbounded if drawn plane without cycles: \(n-(n-1)+1=2\). Euler OK.

Example 19 — Nonplanar with small \(\chi\)

\(K_{3,3}\): nonplanar, yet bipartite so \(\chi=2\). Planarity and chromatic number are related one way (planar ⇒ \(\chi\le 4\)) not the converse.

Example 20 — Degeneracy coloring idea

If every subgraph has a vertex of degree ≤\(k\), repeatedly remove such a vertex; color in reverse removal order with \(k+1\) colors. Planar ⇒ \(k=5\) elementary bound.

Exercises

1. Define proper coloring and \(\chi(G)\).
   
2. Prove \(\chi\ge\omega\).
   
3. Prove \(\chi(G)\le\Delta+1\) by greedy.
   
4. Compute \(\chi\) for \(C_6,C_7,K_{3,3},P_5\).
   
5. Show trees have \(\chi\le 2\).
   
6. Why is \(\chi(C_{2k+1})=3\)?
   
7. State four color theorem.
   
8. Prove \(K_5\) nonplanar via \(m\le 3n-6\).
   
9. Prove \(K_{3,3}\) nonplanar via bipartite planar bound.
   
10. Euler \(n-m+f=2\) for a plane tree (\(f=1\)? tree as plane: \(f=1\), \(n-(n-1)+1=2\) OK).
    
11. Greedy color a 6-vertex graph two different orders—compare colors used.
    
12. Register: build interference for 4 variables with given live overlaps; find \(\chi\).
    
13. True/false: planar ⇒ \(\chi\le 3\). (False: \(K_4\).)
    
14. True/false: \(\chi\le 4\) ⇒ planar. (False.)
    
15. Kuratowski: explain “subdivision” in one sentence.
    
16. Brooks statement for \(\Delta=2\).
    
17. Face coloring ⇔ dual vertex coloring.
    
18. CS: frequency assignment = coloring.
    
19. CS: exam scheduling = coloring.
    
20. Find \(\chi\) of Petersen (awareness 3 or 4?—Petersen \(\chi=3\)).
    
21. Challenge: prove five color theorem outline (optional).
    
22. Maximal planar \(n=6\): \(m=12\); \(\chi\)? (≤4, often 3 or 4).
    
23. Mycielski awareness: high \(\chi\) without triangles.
    
24. Show \(\chi(G\cup H)\) relations optional.
    
25. Portfolio: one nonplanar proof + one register micro-example.

CS connection

• Register allocation via interference graphs.
  
• Scheduling exams/rooms/frequencies.
  
• Map/GIS and layout.
  
• VLSI / circuit board planarity and crossings.
  
• Resource conflict models broadly.

Common pitfalls

Pitfall	What to do instead
\(\chi=\Delta+1\) always	Greedy upper; can be smaller
\(\chi=\omega\) always	Odd cycles, Mycielski
Four color for all graphs	Planar only
\(m\le 3n-6\) for non-simple/nonplanar tests wrong	Hypotheses matter
Exact register \(\chi\) always computed	Heuristics in compilers

Checkpoint

• \(\chi\) definition; \(\omega\le\chi\le\Delta+1\)
  
• Bipartite \(\Leftrightarrow\chi\le 2\)
  
• Four color statement
  
• \(K_5\), \(K_{3,3}\) nonplanar arguments
  
• Register allocation story
  
• Exercises 1–15
  
• Greedy coloring performed by hand

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

4. 2; 3; 2; 2.
   
5. Not bipartite; odd cycle needs 3.
   
6. False (\(K_4\)).
   
7. False (\(K_5\) has \(\chi=5\) actually—bad; \(K_5\) χ=5; use \(K_5\) minor-free… \(\chi=4\) nonplanar examples exist e.g. \(K_{3,3}\) has χ=2 planar? \(K_{3,3}\) nonplanar χ=2. Nonplanar with χ=2: \(K_{3,3}\). So χ≤4 not ⇒ planar.
   
8. Petersen χ=3.

Deepening notes

Greedy coloring worst case

On bipartite graphs, bad order can use many colors temporarily? Actually bipartite \(\chi=2\) but greedy may use more than \(\chi\) though ≤\(\Delta+1\). Example: trees can greedy-use 2 if ordered carefully; still ≤3 for \(\Delta=2\).

Planarity quick kills

• \(K_5\): \(m=10>9\).
  
• \(K_{3,3}\): \(m=9>8=2n-4\).
  
• Subdivision of either: also nonplanar (Kuratowski).

Register allocation micro-exercise (hand)

Live ranges as intervals on a timeline; interference = interval overlap graph = interval graph; color with \(\omega=\max\) depth of overlap.

Extra drills

D1. \(\chi\) of \(K_{2,2,2}\) (octahedral)—optional.
D2. Greedy two orders on \(P_4\).
D3. Prove \(\chi(G)\ge n/\alpha(G)\) sketch.
D4. Euler check for a plane \(K_4\) drawing: \(n-m+f=2\).
D5. Why \(K_{3,3}\) bipartite planar bound.
D6. Interference path of 4 vars—\(\chi\).
D7. Four color vs \(\chi(K_5)=5\) nonplanar.
D8. Map dual: countries adjacent → dual edge.

Flash

\(\omega\le\chi\le\Delta+1\); planar \(\Rightarrow\chi\le 4\); \(m\le 3n-6\); register = color interference graph.

Exam drill block

E1. Compute \(\chi\) for \(E_n,P_n,C_n,K_n,K_{m,n}\).
E2. Prove \(\chi\ge\omega\) and greedy \(\le\Delta+1\).
E3. Greedy color a 6-cycle two orders.
E4. \(K_5\) nonplanar via \(m\le 3n-6\).
E5. \(K_{3,3}\) nonplanar via \(m\le 2n-4\).
E6. Four color statement; show \(K_4\) planar needs 4.
E7. Register: 5 variables with given overlaps—build graph, \(\chi\).
E8. Face vs vertex coloring dual sentence.
E9. Brooks awareness for \(\Delta=3\).
E10. True/false: (i) planar ⇒ \(\chi\le 3\) (ii) \(\chi\le 4\) ⇒ planar (iii) bipartite ⇒ \(\chi\le 2\).

Mini solutions

E1. \(1\); \(2\) (\(n\ge2\)); \(2\) even / \(3\) odd; \(n\); \(2\) if edges.
E10. F; F; T.

Deep dive — Conflict models unified

Coloring is the canonical conflict graph tool:

• Exams conflict → cannot share a slot.
  
• Variables live simultaneously → cannot share a register.
  
• Radios interfere → cannot share a frequency.
  
• Map regions touch → cannot share a print color.

Build \(G\) first; \(\chi(G)\) is the resource count. Lower bound with \(\omega\) (find a clique of mutual conflicts); upper bound with greedy/degeneracy/structure (bipartite, planar, interval).

Synthesis

\(\omega\le\chi\le\Delta+1\) is the everyday sandwich. Bipartite graphs are exactly the graphs with \(\chi\le 2\) (edgeless \(\chi=1\)). Planar graphs satisfy \(\chi\le 4\) (four color) and \(m\le 3n-6\); \(K_5\) and \(K_{3,3}\) are the forbidden-structure gatekeepers. Register allocation is coloring of interference graphs—exact \(\chi\) hard, structure helps.

S1. Prove \(\chi\ge\omega\) and \(\chi\le\Delta+1\) in four sentences total.
S2. Compute \(\chi\) for \(C_8\), \(C_9\), \(K_{2,7}\), and a tree on 10 vertices.
S3. Show \(K_5\) and \(K_{3,3}\) nonplanar with the edge bounds.
S4. Build an interference graph for 5 variables with a specified overlap list; find \(\chi\) and a coloring.
S5. Why does “\(\chi\le 4\)” not imply planar? Give a counterexample class.

Tomorrow

Day 68 — Graphs in CS: dependency, call, CFG, social, routing, state-transition; modeling checklist; complexity culture.