4.2 The vertex coloring problem¶
Part 1 · Combinatorial optimization problems · Chapter 4 · Chapter 4: Coloring problems · Lecture notes, volume 1 (PDF) · Slides · Exercises: Coloring problems · App: Vertex coloring: greedy and DSATUR
Definition 4.3: Vertex Coloring Problem
Given:
-
a simple graph \(G = (V,E)\), where
\[ V = \{1,2,\dots,n\} \]is the set of \(n\) vertices, and
\[ E \subseteq \big\{\, \{u,v\} : u,v \in V,~ u \neq v \,\big\} \]is the set of \(m\) edges,
the Vertex Coloring Problem (VCP) asks to decide how to assign a color to each vertex, so that no two adjacent vertices share the same color, and the total number of colors used is minimized.
-
A VCP instance is specified by:
-
two integer numbers:
-
the number of vertices \(n \in \Z_{\ge 1}\),
-
the number of edges \(m \in \Z_{\ge 1}\),
-
-
two vectors of integer numbers of length \(m\):
-
\(\vet{u} \in \Z_{\ge 1}^m\), containing the first endpoint of the edges,
-
\(\vet{v} \in \Z_{\ge 1}^m\), containing the second endpoint of the edges.
-
-
-
A VCP feasible solution is a family of color classes, i.e., subsets of vertices each assigned to one color,
\[ \mathcal{Q} \subseteq 2^{V} \]such that:
-
(i) \(\mathcal{Q}\) forms a partition of \(V\) into nonempty color classes, namely
\[ \begin{gathered} Q\neq \emptyset, \quad \text{for all } Q\in\mathcal{Q},\\ Q\cap Q'=\emptyset, \quad \text{for all } Q,Q'\in\mathcal{Q}\ \text{with } Q\neq Q',\\ \bigcup_{Q\in\mathcal{Q}} Q=V; \end{gathered} \] -
(ii) each color class in \(\mathcal{Q}\) is a stable set, namely
\[ \{u,v\}\notin E, \quad \text{for all } Q\in\mathcal{Q},\ \text{for all } u,v\in Q\ \text{with } u\neq v. \]
Accordingly, the VCP can be equivalently stated as the problem of determining a partition of the vertex set into color classes such that each color class is a stable set (i.e., its vertices can receive the same color), and the number of color classes (colors) is minimized.
-
Given a VCP instance, the VCP can be formally stated as:
- The optimal value of the VCP is the chromatic number \(\chi(G)\) of the graph: the minimum number of colors (stable sets) needed to color all the vertices. The color classes of a solution are stable sets, and the number of classes is the number of colors used.
Example 4.1: VCP instance: a triangle
We consider the following graph \(G = (V,E)\) with \(3\) vertices (\(n=3\)) and \(3\) edges (\(m=3\)):
The vertex set \(V\) and the edge set \(E\) are:
We call this VCP instance Example 4.1.
Example 4.2: VCP instance: the Petersen graph
We consider now the following graph \(G = (V,E)\) with \(10\) vertices (\(n=10\)) and \(15\) edges (\(m=15\)):
The vertex set \(V\) and the edge set \(E\) are:
We call this VCP instance Example 4.2: it is the reference instance of the chapter.
4.2.1 Assumptions¶
-
We make the following assumptions:
-
The graph has no isolated vertices. An isolated vertex can receive any color used by the rest of the graph; if the graph has no edges, the optimal value is one. Formally:
\[ \deg(v) \ge 1, \qquad \forall\, v \in V. \] -
No vertex has its neighbourhood contained in the neighbourhood of another vertex. Formally:
\[ N(u) \not\subseteq N(v), \qquad \forall\, u,v \in V,~ u \neq v. \]
-
-
The second assumption can be made without loss of generality, because:
-
if \(N(u) \subseteq N(v)\), the vertex \(u\) can be removed without changing the chromatic number: every coloring of \(G \setminus \{u\}\) extends to \(u\) with the color of \(v\);
-
the vertices \(u\) and \(v\) are not adjacent: otherwise \(v \in N(u) \subseteq N(v)\), which is impossible in a simple graph, so \(u\) and \(v\) can share a color.
-
4.2.2 Two simple bounds¶
Observation 4.4: clique bound
For every graph \(G = (V,E)\) we have
Proof
Since all vertices in any clique are pairwise adjacent, they must all receive different colors in any VCP feasible solution. Thus, at least \(\omega(G)\) different colors are needed to color the vertices of any maximum clique, implying \(\omega(G) \le \chi(G)\). □
Observation 4.5: stable set bound
For every graph \(G = (V,E)\) we have
Proof
In a feasible solution with \(k\) color classes, every class is a stable set, so it has at most \(\alpha(G)\) vertices. The \(n\) vertices are covered by the classes, hence \(n \le k \, \alpha(G)\). The number \(k\) is an integer, so \(k \ge \lceil n/\alpha(G) \rceil\). □
- The clique bound is useful when the graph has a large clique, and the stable set bound when its stable sets are small. Both are dual bounds: a clique and a stable set are found without knowing \(\chi(G)\).
4.2.3 Counting the solutions, a first solution and the bounds¶
-
Candidate solutions. The candidate solutions are the partitions of \(V\), counted by the Bell numbers (Chapter 1 «Combinatorial optimization problems»). For Example 4.1 we have \(B(3) = 5\) partitions and only one is feasible: three singletons, since every pair of vertices is adjacent. Hence \(\chi(G) = 3\).
-
For Example 4.2 we have \(B(10) = 115\,975\) partitions, and \(7\,430\) of them are feasible, that is, have only stable sets as classes.
-
A first solution, by eye. The coloring shown in Example 4.2 uses \(3\) colors:
\[ \mathcal{Q} = \big\{\, \{1,4,7,8\},~ \{2,5,6\},~ \{3,9,10\} \,\big\}. \]No edge joins two vertices of the same class, so it is feasible: it is a primal bound, \(\UB = 3 \ge \chi(G)\).
-
Dual bounds on the Petersen graph. The graph has no triangle, so \(\omega(G) = 2\) and the clique bound gives only \(\LB = 2\): a gap of \(1\) remains.
-
The vertices \(1,2,3,4,5\) form a cycle with \(5\) vertices, and so do \(6,7,8,9,10\) (the edges of the figure). A stable set contains at most \(2\) vertices of each cycle, so \(\alpha(G) \le 4\); the set \(\{1,4,7,8\}\) shows that \(\alpha(G) = 4\).
-
The stable set bound gives \(\lceil 10/4 \rceil = 3\). The two bounds coincide: the gap is zero and \(\chi(G) = 3\).
4.3 Remarks¶
-
Brooks (1941) proved that a connected graph that is neither complete nor an odd cycle can be colored with at most \(\Delta\) colors, where \(\Delta\) is the largest degree.
-
Karp (1972) included the chromatic number among his \(21\) NP-complete problems. Garey, Johnson and Stockmeyer (1976) proved that deciding whether \(3\) colors are enough remains NP-complete on planar graphs of maximum degree \(4\).
4.4 Typical mistakes¶
Warning
-
Confusing a clique with a stable set. In a clique all the pairs are edges and the vertices need different colors; in a stable set no pair is an edge and the vertices can share a color.
-
Believing that the clique bound is tight. It is not: the Petersen graph has \(\omega(G) = 2\) and \(\chi(G) = 3\), and the same happens for a cycle with \(5\) vertices.
-
Counting the permutations of the colors as different solutions. A solution is a partition of the vertices into stable sets: exchanging the names of two colors gives the same solution.
-
Using a class that is not a stable set. A color class with two adjacent vertices makes the solution infeasible, whatever the number of colors.
-
Forgetting the assumptions. An isolated vertex and a vertex with \(N(u) \subseteq N(v)\) can be removed before solving, without changing the chromatic number.
4.5 In summary¶
In summary
-
The VCP partitions the vertices of a graph into the minimum number of stable sets; the optimal value is the chromatic number \(\chi(G)\).
-
A clique needs different colors and a stable set can share one; the cliques of \(G\) are the stable sets of the complement graph.
-
A coloring found by eye is a primal bound; the clique bound \(\omega(G)\) and the stable set bound \(\lceil n/\alpha(G) \rceil\) are dual bounds.
-
The bounds do not always meet: on the Petersen graph the clique bound leaves a gap, the stable set bound closes it.
Dashboard of the reference instances.
| instance (min) | lower bound | upper bound | from |
|---|---|---|---|
| Example 4.1 (triangle) | \(3\) (clique bound) | \(3\) (by eye) | this chapter |
| Example 4.2 (Petersen) | \(3\) (stable set bound) | \(3\) (by eye) | this chapter |
Exercises on this chapter: Coloring problems
In depth: what the course does on this problem