Combinatorics • Topic 36

Graph Coloring

Graph coloring involves assigning labels (colors) to vertices or edges subject to certain constraints. It models scheduling, register allocation, and map coloring problems.

Vertex Coloring

Definition (Proper Vertex Coloring)

k

-coloring of a graph

G

is an assignment of

k

colors to vertices such that no two adjacent vertices share the same color.

Chromatic Number

The chromatic number

χ (G)

is the minimum number of colors needed for a proper coloring.

$χ (G) = 1$ : The graph has no edges.
$χ (G) = 2$ : The graph is bipartite.
$χ (K_{n}) = n$ : A complete graph needs $n$ distinct colors.

The Four Color Theorem

Theorem (Four Color Theorem)

Every planar graph (a graph that can be drawn without edge crossings) is 4-colorable.

This means any map on a plane or sphere can be colored with just 4 colors such that adjacent regions have different colors.

Greedy Coloring

A simple algorithm: Order vertices

v_{1}, \dots, v_{n}

. Assign

v_{1}

color 1. For

v_{i}

, assign the smallest color not used by its already-colored neighbors.

Brooks' Theorem: For any connected graph $G$ that is not a complete graph or an odd cycle, $χ (G) \leq Δ (G)$ , where $Δ (G)$ is the maximum degree.

Practice Problems

Exercise (Problem 1)

Find the chromatic number of the cycle graph

C_{5}

Exercise (Problem 2)

Prove that a graph with maximum degree

Δ

can always be colored with

Δ + 1

colors.

Exercise (Problem 3)

Construct a "triangle-free" graph with an arbitrarily large chromatic number (Mycielskian construction).