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 Coloring

• Visit vertices in any order $v_1,v_2,\dots ,v_n$.
• Assign each $v_i$ the smallest color not used by its already-colored neighbors.

Greedy-Coloring(G):
  pick any ordering V = {v₁, ..., vₙ}
  c[v₁] ← 1
  for i = 2 to n:
    c[vᵢ] ← min{ k ∈ ℕ | k ≠ c(u) for all u ∈ N(vᵢ) ∩ {v₁,...,vᵢ₋₁} }

Bound:

$$\chi (G)\le C(G)\le \Delta (G)+1$$

where $\Delta (G)={\max }_{v\in V}\mathrm{deg}(v)$ is the maximum degree.

Runtime: iterating over all nodes and their neighbors $⟹\mathcal{O}(|E|)$

Caveat: The number of colors used depends heavily on vertex ordering. There always exists an ordering achieving $\chi (G)$ colors — but we don’t know which one.

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|})$.