The vertex coloring problem (VCP)¶
Definition 1: The 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.
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.
-
What the course does on this problem¶
| Technique | Where |
|---|---|
| Definition | Ch. 4 «Coloring problems» |
| Formulations | Ch. 11 «Formulations of coloring problems» |
| Heuristics | Ch. 30 «Constructive heuristics» |
| Limits of approximation | Ch. 37 «Vertex coloring: limits of approximation» |
| Ad hoc algorithms | Ch. 42 «Vertex coloring: the DSATUR branch-and-bound» |
| Exercises | Ch. 4 (5 exercises); Ch. 11 (5 exercises); Ch. 30 (3 exercises); Ch. 37 (5 exercises); Ch. 42 (5 exercises) |
Properties¶
-
Strongly NP-hard: deciding whether \(\chi(G)\le 3\) is NP-complete (Ch. 1).
-
Clique bound \(\omega(G) \le \chi(G)\) and stable set bound \(\lceil n/\alpha(G) \rceil \le \chi(G)\) (Ch. 4).
-
The bounds can miss \(\chi(G)\): on the Petersen graph \(\omega(G)=2<\chi(G)=3\) (Ch. 4).
-
Brooks: \(\chi(G)\le\Delta\) for a connected graph that is neither complete nor an odd cycle (Ch. 4).
Formulations¶
-
The model \(\ILP_{\VCP}\) has \(kn\) variables \(x_{vc}\) and \(k\) variables \(y_c\), and \(k!\) equivalent copies of every coloring (Ch. 11).
-
Both LP relaxations have value \(2\) for every graph with an edge (Ch. 11).
-
On the complete graph with \(n\) vertices the gap is \(n-2\) and the ratio \(\frac{2}{n}\) tends to \(0\) (Ch. 11).
Heuristics¶
-
The greedy coloring uses at most \(\Delta(G)+1\) colors, and the order of the vertices matters (Ch. 30).
-
\(DSATUR\) colors first the vertex that sees the most colors; it is exact on bipartite graphs (Ch. 30).
Approximation¶
-
Not approximable: no polynomial algorithm guarantees a ratio below \(\frac43\) unless \(P=NP\), and not even \(n^{1-\varepsilon}\) (Zuckerman) (Ch. 37).
-
Special cases: bipartite and interval graphs exactly, planar graphs within \(2\) colors of the optimum (Ch. 37).