Uniquely colorable graph


In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k−1 independent sets.

Examples

A complete graph is uniquely colorable, because the only proper coloring is one that assigns each vertex a different color.
Every k-tree is uniquely -colorable. The uniquely 4-colorable planar graphs are known to be exactly the Apollonian networks, that is, the planar 3-trees.

Properties

Some properties of a uniquely k-colorable graph G with n vertices and m edges:
  1. m ≥ n - k/2.

    Related concepts

Minimal imperfection

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.

Unique edge colorability

A uniquely edge-colorable graph is a k-edge-chromatic graph that has only one possible k-edge-coloring up to permutation of the colors. The only uniquely 2-edge-colorable graphs are the paths and the cycles. For any k, the stars K1,k are the only uniquely k-edge-colorable graphs. Moreover, conjectured and proved that, when k ≥ 4, they are also the only members in this family. However, there exist uniquely 3-edge-colorable graphs that do not fit into this classification, such as the graph of the triangular pyramid.
If a cubic graph is uniquely 3-edge-colorable, it must have exactly three Hamiltonian cycles, formed by the edges with two of its three colors, but some cubic graphs with only three Hamiltonian cycles are not uniquely 3-edge-colorable.
Every simple planar cubic graph that is uniquely 3-edge-colorable contains a triangle, but observed that the generalized Petersen graph G is non-planar, triangle-free, and uniquely 3-edge-colorable. For many years it was the only known such graph, and it had been conjectured to be the only such graph but now infinitely many triangle-free non-planar cubic uniquely 3-edge-colorable graphs are known.

Unique total colorability

A uniquely total colorable graph is a k-total-chromatic graph that has only one possible k-total-coloring up to permutation of the colors.
Empty graphs, paths, and cycles of length divisible by 3 are uniquely total colorable graphs.
conjectured that they are also the only members in this family.
Some properties of a uniquely k-total-colorable graph G with n vertices:
  1. χ″ = Δ + 1 unless G = K2.
  2. Δ ≤ 2 δ.
  3. Δ ≤ n/2 + 1.
Here χ″ is the total chromatic number; Δ is the maximum degree; and δ is the minimum degree.