7. Colorings

Assign colors to vertices so that no two adjacent vertices share a color. Deciding $\chi (G)\ge 3$ is NP-Complete ☠️.

Chromatic number $\chi (G)$: minimum $k$ for which a valid $k$-coloring exists.

Examples:

• $K_n$: $\chi (K_n)=n$
• Even cycle: $\chi (C_{2n})=2$
• Odd cycle: $\chi (C_{2n+1})=3$
• Trees ($\ge 2$ nodes): $\chi =2$ (they’re bipartite)

---

Bipartite Characterization

Theorem

$G$ bipartite $⟺$ $G$ contains no odd-length cycle as a subgraph.

Proof idea: Run BFS from any vertex $s$. Color vertex $v$ with color $1$ if $d[v]$ is even, color $2$ if odd. No odd cycle $⟹$ no edge connects two same-colored vertices.

---

Four Color Theorem

Theorem

Every planar map can be colored with four colors.

Proved by Appel & Haken (1977) — the theoretical part reduces the problem to finitely many cases, which are then verified by computer.

---

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: $\mathcal{O}(|E|)$ using an adjacency list (for each $v_i$, scan its $\mathrm{deg}(v_i)$ neighbors, mark used colors in a boolean array of size $\mathrm{deg}(v_i)+1$, pick first unused).

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.

example where fails

---

Saving One Color

Two situations where we can beat $\Delta (G)+1$ and achieve $\Delta (G)$ colors in $\mathcal{O}(|E|)$:

Case 1 — Some vertex has $\mathrm{deg}(v)<\Delta (G)$: Start BFS/DFS at $v$, number vertices in reverse traversal order (so $v=v_n$). Then every $v_i$ ($i<n$) has at least one neighbor $v_j$ with $j>i$, leaving at most $\Delta (G)-1$ colored neighbors. The last vertex $v_n=v$ also has $<\Delta (G)$ neighbors. Greedy uses $\le \Delta (G)$ colors.

Case 2 — $k$-regular graph with an articulation vertex: Find the articulation vertex $v$ (modified DFS, $\mathcal{O}(|E|)$). Removing $v$ splits $G$ into components $G_1,\dots ,G_s$. Each $G_i\cup v$ satisfies Case 1, so each is $k$-colorable. Permute colors so $v$ gets the same color in all components $⟹$ combined $k$-coloring of $G$.

---

Brooks’ Theorem

Theorem

If $G$ is a connected graph that is neither $K_n$ nor an odd cycle $C_{2n+1}$, then: $\chi (G)\le \Delta (G)$ A $\Delta (G)$-coloring can be found in $\mathcal{O}(|E|)$.

Why it’s tight: Complete graphs and odd cycles are the only graph types where $\chi (G)=\Delta (G)+1$.

Proof sketch: By the two cases above, we may assume $G$ is $\Delta (G)$-regular with no articulation vertex. Since $G\ne K_n$ but is connected, $\exists v$ with two non-adjacent neighbors $v_1,v_2$. Then either $G\setminus v_1,v_2$ is connected (use Case 1 style ordering starting from $v_1,v_2$) or it splits into components (handle like Case 2, carefully managing color swaps). $\square$

Note: A star shows the max degree doesn’t always govern $\chi$: the center can have arbitrarily large degree, yet $\chi (\text{star})=2$.

---

Degeneracy-Based Coloring

Theorem

If every induced subgraph of $G$ contains a vertex of degree $\le k$, then $\chi (G)\le k+1$, and a $(k+1)$-coloring can be found in $\mathcal{O}(|E|)$.

Algorithm: Repeatedly peel off a vertex of degree $\le k$ (maintaining a queue of low-degree vertices). This gives an ordering $v_1,\dots ,v_n$ where each $v_i$ has $\le k$ neighbors among $v_1,\dots ,v_i$. Greedy then needs $\le k+1$ colors.

Runtime: $\mathcal{O}(|E|)$ — maintain degree array $d[]$ and a queue $Q$ of vertices with $d[v]\le k$. Each edge is processed at most twice.

---

Mycielski Construction — Triangle-Free but High $\chi$

Theorem

For all $k\ge 2$, there exists a triangle-free graph $G_k$ with $\chi (G_k)\ge k$.

Construction (inductive):

• Base: $k=2$: a single edge.
• Step $k\to k+1$: Given $G_k$ with vertices $v_1,\dots ,v_n$:
  1. Add a “shadow” vertex $w_i$ for each $v_i$, connected to all neighbors of $v_i$ (but not to $v_i$ itself).
  2. Add one extra vertex $z$ connected to all $w_1,\dots ,w_n$.

Why it works:

• Still triangle-free: The $w_i$ are not connected to each other, so $z$ is in no triangle. Any triangle involving $w_i$ would require a triangle in $G_k$ (which is triangle-free).
• Chromatic number increases: Assume $G_{k+1}$ is $k$-colorable. Then some color is absent from $z$‘s neighborhood. Since $w_i$ and $v_i$ have the same neighbors in $G_k$, we can recolor $v_i$ to $w_i$‘s color wherever needed, producing a $(k-1)$-coloring of $G_k$ — contradiction.

---

Coloring 3-Chromatic Graphs

Given a graph promised to be 3-colorable, we can’t efficiently find the 3-coloring (that’s NP-hard). But we can do better than $\Delta (G)+1$:

Theorem

Every 3-colorable graph $G=(V,E)$ can be colored with $\mathcal{O}(\sqrt{|V|})$ colors in $\mathcal{O}(|E|)$ time.

Key insight: In a 3-coloring, every vertex’s neighborhood is bipartite (only 2 remaining colors). So $G[N(v)]$ can be 2-colored via BFS.

Algorithm:

1. While $\exists$ a vertex $v$ with $\mathrm{deg}(v)\ge \sqrt{n}$: color $v$ and its neighborhood with 3 new colors (possible since $G[N(v)]$ is bipartite). Remove them.
2. Once all remaining degrees $<\sqrt{n}$: apply Brooks’ theorem $⟹\le \sqrt{n}$ colors.

Color count: Step 1 runs $\le \sqrt{n}$ times (each round removes $\ge \sqrt{n}$ vertices), using $\le 3\sqrt{n}$ colors. Step 2 adds $\le \sqrt{n}$. Total: $\mathcal{O}(\sqrt{n})$.

State of the art: Coloring with 4 colors is NP-hard, but $\mathcal{O}(|V{|}^{0.211})$ colors suffices (improving the $\mathcal{O}(|V{|}^{0.5})$ bound above).