Uniquely colorable graph

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors.

Example 1. A minimal imperfect graph is a graph in which every subgraph is perfect. The deletion of any vertex from a minimal imperfect graph leaves a uniquely colorable subgraph.

Some properties of a uniquely colorable graph G with n vertices and m edges:

1. m ≥ (k - 1) n - C(k, 2), where C(k, 2) = k(k-1)/2. (Xu 1990)

A uniquely edge-colorable graph is a k-edge-chromatic graph that has only one possible (proper) k-edge-coloring up to permutation of the colors.

Example 2. A graph theoretic hypercube Q_k is defined recursively such that Q₀ = K₁ (a single vertex) and that, for all positive integers k, Q_k is obtained by adding an edge to each pair of corresponding vertices between two copies of Q_k-1. A hypercube is uniquely k-edge-colorable.

References

• Xu, Shaoji (1990). The size of uniquely colorable graphs. J. Combin. Theory (B) 50, 319–320.