A uniquely colorable graph is a simple undirected graph $G$ that possesses exactly one proper vertex‑coloring using its chromatic number $\chi(G)$ colors, up to a permutation of the colors. In other words, any two proper $\chi(G)$-colorings of $G$ can be obtained from one another by simply renaming the colors.
Formal definition
Let $G=(V,E)$ be a graph and let $\chi(G)$ denote its chromatic number. A proper vertex‑coloring is a function $c:V\to{1,\dots ,k}$ such that adjacent vertices receive distinct colors.
$G$ is uniquely colorable if for $k=\chi(G)$ the set of proper $k$-colorings consists of a single equivalence class under the action of the symmetric group $S_k$ (the group of permutations of the $k$ colors).
Basic properties
| Property | Description |
|---|---|
| Vertex‑critical | Every uniquely colorable graph is $\chi$-critical: removing any vertex reduces the chromatic number, i.e., $\chi(G-v) < \chi(G)$ for all $v\in V$. |
| Edge‑critical | Some uniquely colorable graphs are also edge‑critical: deleting any edge lowers the chromatic number. However, edge‑criticality is not required by the definition. |
| Clique number | The size of a maximum clique $\omega(G)$ satisfies $\omega(G)=\chi(G)$. Consequently, uniquely colorable graphs are perfect with respect to the equality $\omega=\chi$. |
| Automorphisms | The only color‑preserving automorphisms of a uniquely colorable graph are those that permute colors; any non‑trivial graph automorphism must correspond to a permutation of the color classes. |
| Existence | For every integer $k\ge 2$ there exist uniquely $k$-colorable graphs. Simple examples include the complete graph $K_k$ and the odd cycle $C_{2k+1}$ (which is uniquely $(k+1)$-colorable). |
Examples
- Complete graphs $K_k$: Every vertex must receive a distinct color, so the only proper $k$-coloring is the trivial assignment up to permutation of colors.
- Odd cycles $C_{2m+1}$: The chromatic number is 3; any proper 3‑coloring forces alternating colors around the cycle, leaving only a single coloring pattern modulo color permutation.
- Mycielski constructions: Certain graphs obtained via the Mycielski operation on uniquely colorable graphs retain unique colorability while increasing the chromatic number.
Known results
- Uniquely colorable critical graphs: A graph that is both uniquely colorable and vertex‑critical is called a uniquely critical graph. It has been shown that every uniquely critical graph is edge‑critical as well (see literature on critical graphs).
- Bound on minimum degree: For a uniquely $k$-colorable graph $G$ with $k\ge 3$, the minimum degree $\delta(G)$ satisfies $\delta(G)\ge k-1$. This follows from the necessity of each vertex to be adjacent to vertices of all other color classes.
- NP‑completeness: Determining whether a given graph is uniquely $\chi(G)$-colorable is co‑NP‑complete, because verifying the existence of a second distinct proper coloring can be reduced to the standard graph‑coloring decision problem.
Applications
Uniquely colorable graphs arise in the study of graph coloring rigidity, where the uniqueness of a coloring models constraints in scheduling, frequency assignment, and puzzle design (e.g., Sudoku variants). The concept also assists in constructing graphs with prescribed chromatic properties for extremal combinatorial investigations.
References (selected)
- J. Jensen and B. Toft, Graph Coloring Problems, Wiley, 1995 – Chapter 9 discusses uniquely colorable graphs and related criticality results.
- M. M. Nešetřil, “Uniquely colorable graphs”, Discrete Mathematics 197 (1999) 81–93.
- D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001 – Section on critical and uniquely colorable graphs.
These sources provide formal definitions, proofs of the properties listed above, and a broader bibliography for further reading.
