Uniquely colorable graph

In mathematics, 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.

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.