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

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:

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

Paths

A path with at least two vertices is bipartite. Alternating colors along the path gives a proper coloring.

Thus:

for $n \ge 2$.

Cycles

Even cycles are bipartite, so:

Odd cycles are not bipartite. Two alternating colors fail when the cycle closes. A third color is necessary.

\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

then each set

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:

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:

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

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:

For a graph containing at least one edge:

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:

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:

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:

68.8 Critical Graphs

A graph $G$ is $k$-critical if:

and removing any vertex lowers the chromatic number.

Thus:

for every vertex $v$.

Critical graphs are minimal obstructions to $(k-1)$-colorability.

Examples include:

Critical graphs are important because many coloring proofs proceed by studying minimal counterexamples.

68.9 Brooks’ Theorem

The bound

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:

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)\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

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:

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

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:

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:

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.

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:

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:

Coloring problems are deceptively simple to state. Their solutions range from elementary arguments to deep structural theorems and computational complexity theory.