5. Colorings

Greedy: can find $\le \Delta (G)+1$

planar (all in plane without edge overlap): $\chi \le 4$ by the Four Color Theorem. By Heuristic: possible $\le 6$

2-colorable: linear time

even cycles are 2-colorable odd cycles are 3-colorable

a graph is bipartite $⟺$ no subgraph is cycle of uneven length

a block graph, where each block can be colored with at most $k$ colors, can be colored with $k$ colors

Brooks’ Theorem

Theorem

For any connected graph $G$ that is neither a complete graph nor an odd cycle (the entire graph), the chromatic number satisfies

$$\chi (G)\le \Delta (G)$$

where $\Delta (G)$ is the maximum degree of $G$

Greedy Algorithm

• Chose an arbitrary edge order
• Assign color 1 to $v_1$

Heuristic

• Order nodes with ascending degree

3-Colorable Algorithm

A 3-colorable graph can always be colored in $\mathcal{O}(|V|+|E|)$ with $\mathcal{O}(\sqrt{|V|})$.