Chapter 66. Vertex Coloring

Vertex coloring is the assignment of labels, called colors, to the vertices of a graph. The purpose is usually to separate adjacent vertices. Two vertices joined by an edge represent a conflict: they cannot receive the same color.

This idea turns a graph into a model of incompatibility. If vertices are tasks, an edge may mean that two tasks cannot occur at the same time. If vertices are radio transmitters, an edge may mean that two transmitters interfere. If vertices are exams, an edge may mean that some student must take both exams. A coloring assigns resources so that conflicts are respected.

66.1 Coloring a Graph

Let $G = (V,E)$ be a graph. A vertex coloring of $G$ is a function

where $S$ is a set of colors.

If $S = \{1,2,\ldots,k\}$, then $c$ is called a $k$-coloring. The value $c(v)$ is the color assigned to the vertex $v$.

A coloring is proper if adjacent vertices receive different colors. Thus, for every edge $uv \in E$,

This is the main form of coloring studied in elementary graph theory. Unless stated otherwise, a coloring in this chapter means a proper vertex coloring.

66.2 Color Classes

Given a coloring $c : V \to S$, each color determines a subset of vertices:

The set $V_i$ is called a color class.

In a proper coloring, no two adjacent vertices lie in the same color class. Therefore each color class is an independent set. Conversely, if the vertex set of a graph can be partitioned into $k$ independent sets, then the graph has a proper $k$-coloring.

Thus vertex coloring may be viewed in two equivalent ways.

The partition view is often more useful in proofs. The function view is often more useful in algorithms.

66.3 $k$-Colorable Graphs

A graph $G$ is $k$-colorable if it has a proper coloring using at most $k$ colors.

If $G$ is $k$-colorable, then it is also $(k+1)$-colorable. The extra color may simply remain unused. Therefore colorability is monotone in the number of allowed colors.

The smallest useful values have special names.

A graph is 1-colorable exactly when no edge is present. If an edge $uv$ exists, then $u$ and $v$ must receive different colors.

A graph is 2-colorable exactly when it is bipartite. The two color classes form the two parts of the bipartition.

66.4 Chromatic Number

The chromatic number of a graph $G$, denoted $\chi(G)$, is the least number of colors needed in a proper vertex coloring.

This definition is standard: the chromatic number is the minimum number of colors in a proper coloring.

A coloring using exactly $\chi(G)$ colors is called an optimal coloring. A graph with chromatic number $k$ is called $k$-chromatic.

For example:

In a complete graph $K_n$, every pair of distinct vertices is adjacent. Therefore no two vertices may share a color. All $n$ vertices require distinct colors.

For a cycle $C_n$,

An even cycle alternates between two colors. An odd cycle cannot be colored with two colors, because the alternating pattern returns to the starting point with a conflict.

66.5 Examples

Consider the path graph $P_4$:

A proper 2-coloring is given by

Thus

Now consider the triangle $K_3$. Each vertex is adjacent to the other two. If one vertex receives color 1 and another receives color 2, the third vertex is adjacent to both, so it requires a third color. Hence

Now consider the square $C_4$. Opposite vertices may share colors, and adjacent vertices differ. Thus

These examples show that the number of vertices alone does not determine the chromatic number. The edge structure determines which vertices may share colors.

66.6 Basic Bounds

Every finite graph $G$ satisfies

when $V(G)$ is nonempty.

The upper bound is obtained by assigning a distinct color to every vertex. This is always proper. The lower bound follows because at least one color is required for a nonempty graph.

A better upper bound uses the maximum degree. Let $\Delta(G)$ be the maximum degree of $G$. Then

To see this, order the vertices in any way and color them one by one. When a vertex $v$ is colored, at most $\Delta(G)$ of its neighbors have already received colors. Therefore among $\Delta(G)+1$ available colors, at least one color remains available for $v$.

This argument gives a simple greedy coloring proof. It also shows that local degree information gives a global coloring bound.

66.7 Cliques and Lower Bounds

A clique is a set of vertices that are pairwise adjacent. If a graph contains a clique of size $r$, then those $r$ vertices must all receive different colors. Therefore

where $\omega(G)$ is the clique number of $G$, the size of a largest clique.

This lower bound is often useful, but it need not be exact. Some graphs require many colors even when their largest clique is small. Odd cycles of length at least five have clique number $2$ but chromatic number $3$.

The gap between clique number and chromatic number is one of the central themes of coloring theory.

66.8 Bipartite Graphs as 2-Colorable Graphs

A graph is bipartite if its vertex set can be written as a disjoint union

such that every edge has one endpoint in $A$ and one endpoint in $B$.

This is exactly the same as a proper 2-coloring. Assign color 1 to every vertex in $A$, and color 2 to every vertex in $B$. Since no edge lies inside $A$ or inside $B$, adjacent vertices receive different colors.

Conversely, if a graph has a proper 2-coloring, the two color classes form a bipartition.

Thus:

For a graph with at least one edge,

66.9 Greedy Coloring

The greedy coloring algorithm colors vertices one at a time. At each step, it assigns the smallest available color that does not conflict with already colored neighbors.

The algorithm depends on the chosen vertex order.

Suppose the vertices are ordered as

For each $v_i$, assign the smallest color not used by any previously colored neighbor of $v_i$.

Greedy coloring always produces a proper coloring. However, it may use more colors than necessary. The same graph may receive different numbers of colors under different vertex orders.

This behavior is important. Coloring is partly structural and partly algorithmic. A graph may have a small chromatic number, while a poor coloring order causes a simple algorithm to use more colors.

66.10 Coloring and Scheduling

Vertex coloring gives a clean model for scheduling conflicts.

Let each vertex represent an event. Put an edge between two vertices if the two events cannot occur at the same time. A proper coloring assigns time slots to events so that conflicting events receive different slots.

In this model:

For example, in exam scheduling, each exam is a vertex. Two exams are adjacent if some student is enrolled in both. A coloring assigns exam periods. A proper coloring ensures that no student has two exams at the same time.

The chromatic number is the smallest number of periods needed.

66.11 Coloring and Maps

Map coloring is another classical source of graph coloring.

Given a map divided into regions, construct a graph as follows. Each region becomes a vertex. Two vertices are joined by an edge when the corresponding regions share a boundary segment.

A proper vertex coloring of this graph assigns colors to regions so that neighboring regions have different colors.

This converts a geometric problem into a graph problem. The Four Color Theorem states that every planar graph can be colored with at most four colors. In graph-theoretic language, if $G$ is planar, then

This theorem is deep. It belongs to planar graph theory, but vertex coloring gives its language.

66.12 Critical Graphs

A graph $G$ is color-critical, or simply critical, if removing any vertex lowers its chromatic number. More precisely, $G$ is $k$-critical if

and

for every vertex $v \in V(G)$.

Critical graphs isolate the obstruction to coloring with fewer colors. For example, $K_k$ is $k$-critical. Odd cycles are 3-critical.

Critical graphs are useful because many coloring arguments reduce to minimal counterexamples. If a theorem about $k$-colorability fails, one can often choose a smallest counterexample. Such a graph usually has critical structure.

66.13 Coloring Subgraphs

If $H$ is a subgraph of $G$, then

Any proper coloring of $G$ restricts to a proper coloring of $H$. Removing vertices or edges cannot force the use of more colors.

This monotonicity gives immediate lower bounds. If $G$ contains a subgraph $H$ whose chromatic number is known, then $G$ must use at least as many colors as $H$.

For example, if $G$ contains a triangle, then

If $G$ contains $K_5$, then

66.14 Common Chromatic Numbers

Several standard graph families have simple chromatic numbers.

A tree with at least two vertices is bipartite, hence 2-colorable. Since it has at least one edge, it cannot be 1-colorable. Therefore its chromatic number is 2.

66.15 The Role of Vertex Coloring

Vertex coloring belongs to the structural part of graph theory, but it also has algorithmic and applied significance.

Structurally, coloring measures how far a graph is from being independent or bipartite. It studies the tension between adjacency and grouping.

Algorithmically, coloring asks for efficient methods to assign colors. Some coloring problems are easy, such as testing whether a graph is 2-colorable. Others are computationally difficult; determining chromatic number is generally hard for large graphs, and even planar coloring can involve difficult decision problems.

In applications, coloring converts conflict constraints into a discrete allocation problem. The same formal model appears in scheduling, register allocation, frequency assignment, map coloring, and resource sharing.

66.16 Exercises

1. Find the chromatic number of $P_5$.

2. Find the chromatic number of $C_5$.

3. Prove that every complete graph $K_n$ has chromatic number $n$.

4. Prove that every bipartite graph is 2-colorable.

5. Give an example of a graph with clique number $2$ and chromatic number $3$.

6. Apply greedy coloring to $C_6$ using the natural cyclic order of the vertices.

7. Find an ordering of the vertices of a bipartite graph for which greedy coloring uses more than two colors.

8. Prove that if $H$ is a subgraph of $G$, then $\chi(H) \le \chi(G)$.

9. Construct the conflict graph for four exams where exam pairs $(A,B)$, $(A,C)$, and $(C,D)$ conflict. Find a minimum coloring.

10. Prove that a graph is 1-colorable if and only if it has no edges.