Graph Coloring — Mathematics Knowledge System

Overview

Graph coloring assigns labels ('colors') to the vertices of a graph so that no two adjacent vertices share the same color. The chromatic number χ(G) is the minimum number of colors needed. Coloring problems are notoriously hard in general (determining χ(G) is NP-hard), but the concept models an enormous range of scheduling and assignment problems, from exam timetabling to register allocation in compilers to the famous Four Color Theorem, which states that any planar map can be colored with just four colors so no two adjacent regions share a color.

Intuition

Picture scheduling final exams: courses are vertices, and an edge connects two courses if some student is taking both (so they can't be scheduled at the same time). Coloring the graph with time slots as colors, so adjacent courses get different colors, gives a valid exam schedule — and the chromatic number tells you the fewest time slots you could possibly need.

Formal Definition

Definition

A proper coloring assigns colors so adjacent vertices differ, and the chromatic number is the smallest such count:

c: V \to \{1, \dots, k\} \text{ such that } \{u,v\} \in E \Rightarrow c(u) \ne c(v)

Proper k-coloring

\chi(G) = \min\{k : G \text{ has a proper } k\text{-coloring}\}

Chromatic number

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

Greedy coloring bound (Δ = maximum degree)

Worked Examples

Try 2 colors: A=1, B must differ from A so B=2, but C is adjacent to BOTH A and B, so C needs a color different from both 1 and 2 — impossible with only 2 colors.
$\chi(G) > 2$
With 3 colors: A=1, B=2, C=3. Every pair is adjacent and gets a different color, so this works.
$\chi(G) = 3$

Answer: χ(triangle) = 3.

Practice Problems

Difficulty 3/10

What is the chromatic number of a graph with vertices {A,B,C,D} and no edges at all?

Difficulty 5/10

5 exams need scheduling. Exams that share a student can't be at the same time, forming a 'conflict graph' where the maximum clique (mutually conflicting set) has size 4. What is the minimum possible number of time slots, and why can it not be less than 4?

Difficulty 4/10

According to the Four Color Theorem, what is the maximum chromatic number of any planar graph (e.g., a map of countries where adjacent countries must differ in color)?

Quiz

Summary

Graph coloring assigns colors to vertices so adjacent vertices always differ; χ(G) is the minimum number of colors needed.
χ(G) ≥ ω(G) (the largest clique size) and χ(G) ≤ Δ(G) + 1 (greedy bound via maximum degree).
The Four Color Theorem guarantees χ(G) ≤ 4 for any planar graph, resolving the classic map-coloring problem.

References

WebsiteWikipedia — Graph coloring