Graph Coloring

Vertex Coloring

Definition

A proper vertex coloring assigns colors to vertices so that no two adjacent vertices have the same color.

A graph is $k$-colorable if it can be properly colored with $k$ colors.

Chromatic Number

The chromatic number $\chi(G)$ is the minimum number of colors needed: $\chi(G) = \min\{k : G \text{ is } k\text{-colorable}\}$

Basic Examples

Complete Graph $K_n$

$\chi(K_n) = n$ Every vertex is adjacent to every other.

Cycle $C_n$

$\chi(C_n) = \begin{cases} 2 & \text{if } n \text{ is even} \\ 3 & \text{if } n \text{ is odd} \end{cases}$

Bipartite Graph

$\chi(G) = 2 \text{ if } G \text{ is bipartite and has edges}$ $\chi(G) = 1 \text{ if } G \text{ has no edges}$

Tree

$\chi(T) = 2 \text{ (if at least one edge)}$

Bounds on Chromatic Number

Upper Bounds

Greedy bound: $\chi(G) \leq \Delta(G) + 1$ where $\Delta(G)$ is maximum degree.

Brooks' Theorem: For connected graph $G$ that is neither complete nor an odd cycle: $\chi(G) \leq \Delta(G)$

Lower Bounds

Clique bound: $\chi(G) \geq \omega(G)$ where $\omega(G)$ is the size of the largest clique.

Independence bound: $\chi(G) \geq \frac{|V|}{\alpha(G)}$ where $\alpha(G)$ is the independence number (largest independent set).

Chromatic Polynomial

The chromatic polynomial $P(G, k)$ gives the number of proper $k$-colorings.

Examples

Empty graph $\overline{K_n}$: $P(\overline{K_n}, k) = k^n$

Complete graph $K_n$: $P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1) = k^{\underline{n}}$

Cycle $C_n$: $P(C_n, k) = (k-1)^n + (-1)^n(k-1)$

Tree with $n$ vertices: $P(T, k) = k(k-1)^{n-1}$

Deletion-Contraction

For edge $e = (u,v)$: $P(G, k) = P(G - e, k) - P(G / e, k)$

where $G - e$ deletes edge $e$ and $G / e$ contracts edge $e$.

Four Color Theorem

Every planar graph is 4-colorable. $\chi(G) \leq 4 \text{ for planar } G$

Proved in 1976 (Appel and Haken) using computer verification.

Five Color Theorem: Easier to prove: every planar graph is 5-colorable.

Edge Coloring

Definition

A proper edge coloring assigns colors to edges so that no two edges sharing a vertex have the same color.

Chromatic Index

$\chi'(G)$ = minimum number of colors for proper edge coloring.

Vizing's Theorem

For any simple graph $G$: $\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1$

Graphs achieving lower bound: Class 1 Graphs requiring upper bound: Class 2

Examples

• Bipartite graphs: $\chi'(G) = \Delta(G)$ (Class 1)
• Petersen graph: $\chi'(G) = 4 = \Delta(G) + 1$ (Class 2)

Greedy Coloring Algorithm

1. Order vertices: v_1, v_2, ..., v_n
2. For each v_i in order:
   Assign v_i the smallest color not used by its neighbors

Always uses $\leq \Delta(G) + 1$ colors, but ordering matters.

Applications

Scheduling

Tasks as vertices, edge if tasks conflict. Colors = time slots. $\chi(G)$ = minimum time slots needed.

Register Allocation

Variables as vertices, edge if both needed simultaneously. Colors = CPU registers.

Map Coloring

Regions as vertices, edge if regions share a border. Four colors suffice for any map.

Frequency Assignment

Transmitters as vertices, edge if too close. Colors = frequencies.

Graph Coloring Complexity

Decision problem: Is $G$ $k$-colorable?

• $k = 2$: Polynomial (bipartite testing)
• $k \geq 3$: NP-complete

Computing chromatic number: NP-hard

Special Classes

Chordal Graphs

Graphs where every cycle of length $\geq 4$ has a chord. Can be optimally colored in polynomial time.

Perfect Graphs

Graphs where $\chi(H) = \omega(H)$ for all induced subgraphs $H$. Includes bipartite, chordal, and complement of bipartite.