Chapter 68. Chromatic Number
Chapter 68. Chromatic Number
The chromatic number measures the minimum number of colors needed to color a graph properly. It is one of the central numerical invariants of graph theory.
A graph with small chromatic number has a simple conflict structure. A graph with large chromatic number contains strong adjacency constraints. The study of chromatic number asks how graph structure forces or restricts colorability.
Many deep questions in graph theory are fundamentally questions about chromatic number.
68.1 Definition
Let (G = (V,E)) be a graph.
A proper vertex coloring is an assignment of colors to vertices such that adjacent vertices receive different colors.
The chromatic number of (G), denoted
$$ \chi(G), $$
is the minimum number of colors needed for a proper coloring.
\chi(G)=\min{k:G\text{ is }k\text{-colorable}}
A graph requiring exactly (k) colors is called (k)-chromatic.
The chromatic number measures how difficult it is to separate adjacent vertices into independent classes.
68.2 First Examples
The simplest examples establish the basic behavior.
Empty Graph
If (G) has no edges, then no adjacency restrictions exist. Every vertex may receive the same color.
Thus:
$$ \chi(G)=1. $$
Complete Graph
In the complete graph (K_n), every pair of distinct vertices is adjacent. Therefore every vertex requires its own color.
$$ \chi(K_n)=n. $$
\chi(K_n)=n
Paths
A path with at least two vertices is bipartite. Alternating colors along the path gives a proper coloring.
Thus:
$$ \chi(P_n)=2 $$
for (n \ge 2).
Cycles
Even cycles are bipartite, so:
$$ \chi(C_{2m})=2. $$
Odd cycles are not bipartite. Two alternating colors fail when the cycle closes. A third color is necessary.
$$ \chi(C_{2m+1})=3. $$
\chi(C_n)=\begin{cases}2,&n\text{ even}\3,&n\text{ odd}\end{cases}
Parity therefore plays a fundamental role in coloring.
68.3 Color Classes
A coloring partitions the vertex set into subsets of equal color.
If
$$ c : V \to {1,2,\ldots,k}, $$
then each set
$$ V_i = {v \in V : c(v)=i} $$
is called a color class.
Because adjacent vertices cannot share a color, every color class is an independent set.
Thus a proper coloring is equivalent to partitioning the vertex set into independent sets.
The chromatic number may therefore be interpreted as the minimum number of independent sets needed to cover all vertices.
68.4 Basic Bounds
The chromatic number satisfies several immediate bounds.
For every nonempty graph:
$$ 1 \le \chi(G) \le |V(G)|. $$
The lower bound is obvious. The upper bound follows by assigning a different color to every vertex.
More useful bounds involve graph structure.
Clique Bound
If (G) contains a clique of size (r), then those (r) vertices must all receive different colors.
Therefore:
$$ \chi(G)\ge \omega(G), $$
where (\omega(G)) is the clique number.
\chi(G)\ge\omega(G)
This is one of the most important lower bounds.
Degree Bound
Let (\Delta(G)) denote the maximum degree of (G).
A greedy coloring argument shows:
$$ \chi(G)\le \Delta(G)+1. $$
\chi(G)\le\Delta(G)+1
The proof colors vertices one at a time. Each vertex has at most (\Delta(G)) colored neighbors, so among (\Delta(G)+1) colors at least one remains available.
68.5 Bipartite Graphs
A graph is bipartite if its vertex set may be partitioned into two independent sets.
This means exactly that the graph is 2-colorable.
Thus:
$$ G \text{ bipartite} \quad\Longleftrightarrow\quad \chi(G)\le 2. $$
For a graph containing at least one edge:
$$ G \text{ bipartite} \quad\Longleftrightarrow\quad \chi(G)=2. $$
A graph is bipartite precisely when it contains no odd cycle. Therefore odd cycles are the basic obstruction to 2-colorability.
68.6 Greedy Coloring
Greedy coloring is the simplest coloring algorithm.
Choose an ordering of the vertices:
$$ v_1,v_2,\ldots,v_n. $$
Color vertices one by one. For each vertex, assign the smallest available color not already used by colored neighbors.
The algorithm always produces a proper coloring.
However, the number of used colors depends strongly on the chosen order.
A poor ordering may use many more colors than necessary. A good ordering may achieve an optimal coloring.
Thus coloring is both structural and algorithmic.
68.7 Chromatic Number and Subgraphs
If (H) is a subgraph of (G), then:
$$ \chi(H)\le \chi(G). $$
Removing edges or vertices cannot make coloring harder.
This monotonicity provides useful lower bounds. If (G) contains a subgraph with large chromatic number, then (G) must also require many colors.
For example:
| Subgraph contained in (G) | Consequence |
|---|---|
| Triangle (K_3) | (\chi(G)\ge 3) |
| Complete graph (K_5) | (\chi(G)\ge 5) |
| Odd cycle | (G) not bipartite |
68.8 Critical Graphs
A graph (G) is (k)-critical if:
$$ \chi(G)=k $$
and removing any vertex lowers the chromatic number.
Thus:
$$ \chi(G-v)<k $$
for every vertex (v).
Critical graphs are minimal obstructions to ((k-1))-colorability.
Examples include:
| Graph | Criticality |
|---|---|
| (K_n) | (n)-critical |
| Odd cycles | 3-critical |
Critical graphs are important because many coloring proofs proceed by studying minimal counterexamples.
68.9 Brooks' Theorem
The bound
$$ \chi(G)\le \Delta(G)+1 $$
is usually not sharp.
Brooks' Theorem gives a stronger result.
If (G) is a connected graph that is neither a complete graph nor an odd cycle, then:
$$ \chi(G)\le \Delta(G). $$
Thus only complete graphs and odd cycles truly require the extra color.
This theorem is one of the central structural results in coloring theory.
68.10 Chromatic Number and Density
Dense graphs often require many colors, but density alone does not determine chromatic number.
Complete graphs are extremely dense and have large chromatic number. Sparse graphs often have small chromatic number.
However, sparse graphs with arbitrarily large chromatic number also exist.
This surprising fact was first demonstrated probabilistically by Paul Erdős.
There exist graphs with:
- arbitrarily large girth,
- arbitrarily large chromatic number.
Thus large chromatic number cannot be explained solely by short cycles or local density.
This result changed the direction of extremal graph theory and probabilistic graph theory.
68.11 Coloring Planar Graphs
A planar graph can be drawn in the plane without edge crossings.
Coloring planar graphs led historically to one of the most famous problems in mathematics.
The Four Color Theorem states:
Every planar graph satisfies
$$ \chi(G)\le 4. $$
\chi(G)\le4
for planar (G).
This theorem was proved using extensive computer assistance by Kenneth Appel and Wolfgang Haken in 1976.
The theorem says that every planar map may be colored using at most four colors so that neighboring regions differ.
Planar coloring remains a major area of graph theory.
68.12 Coloring Algorithms
Determining chromatic number is computationally difficult.
Given a graph (G) and an integer (k), deciding whether
$$ \chi(G)\le k $$
is NP-complete for every fixed (k\ge 3).
Thus no efficient general algorithm is known.
Even approximate coloring is difficult in many cases.
Nevertheless, practical algorithms exist for many graph classes:
| Graph class | Coloring complexity |
|---|---|
| Bipartite graphs | Easy |
| Trees | Easy |
| Interval graphs | Efficient |
| Perfect graphs | Polynomial-time |
| General graphs | NP-hard |
This gap between theory and computation is one reason coloring theory remains active.
68.13 Perfect Graphs
A graph (G) is perfect if every induced subgraph (H) satisfies
$$ \chi(H)=\omega(H). $$
Thus clique number completely determines chromatic number throughout the graph.
Perfect graphs form one of the most important structural classes in graph theory.
Examples include:
| Graph type | Perfect? |
|---|---|
| Bipartite graphs | Yes |
| Complete graphs | Yes |
| Interval graphs | Yes |
| Chordal graphs | Yes |
Odd cycles of length at least five are not perfect.
Perfect graph theory connects coloring, optimization, and polyhedral combinatorics.
68.14 Fractional and Approximate Coloring
The classical chromatic number requires whole colors assigned discretely.
More flexible notions also exist.
Fractional Coloring
Vertices may share colors fractionally. This leads to the fractional chromatic number:
$$ \chi_f(G). $$
Fractional coloring connects graph theory with linear programming.
Approximate Coloring
Algorithms may seek near-optimal colorings rather than exact optimum colorings.
Approximation theory studies how closely efficient algorithms can approach the true chromatic number.
These generalized coloring concepts are important in optimization and theoretical computer science.
68.15 Applications
Chromatic number appears naturally in many applications.
| Application | Meaning of colors |
|---|---|
| Exam scheduling | Time slots |
| Register allocation | CPU registers |
| Frequency assignment | Radio frequencies |
| Map coloring | Geographic regions |
| Task scheduling | Shared resources |
| Constraint satisfaction | Compatible assignments |
The graph models incompatibility. Coloring resolves the incompatibilities with minimal resources.
68.16 Extremal Questions
Many advanced questions ask how graph structure constrains chromatic number.
Typical problems include:
| Question | Example |
|---|---|
| Maximum chromatic number under constraints | Triangle-free graphs |
| Minimum edges forcing (k)-chromaticity | Critical graphs |
| Chromatic number vs girth | Erdős constructions |
| Chromatic number vs minors | Hadwiger-type problems |
These questions connect coloring with topology, probability, geometry, and combinatorics.
68.17 Summary
The chromatic number is one of the central invariants of graph theory.
It measures the minimum number of independent classes needed to partition the vertex set.
The subject combines:
| Aspect | Focus |
|---|---|
| Structural | Cliques, cycles, critical graphs |
| Algorithmic | Efficient coloring methods |
| Extremal | Bounds and constructions |
| Applied | Scheduling and allocation |
| Computational | Complexity and approximation |
Coloring problems are deceptively simple to state. Their solutions range from elementary arguments to deep structural theorems and computational complexity theory.