Editing Uniquely colorable graph (section)

==Related concepts==
===Minimal imperfection===
A ''minimal imperfect graph'' is a graph in which every subgraph is [[perfect graph|perfect]].  The deletion of any vertex from a minimal imperfect graph leaves a uniquely colorable subgraph.

===Unique edge colorability===
[[File:Generalized Petersen 9 2 edge coloring.svg|thumb|The unique 3-edge-coloring of the [[generalized Petersen graph]] ''G''(9,2)]]
A '''uniquely edge-colorable graph''' is a [[Edge coloring|''k''-edge-chromatic]] graph that has only one possible [[Edge coloring|(proper) ''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 [[Star (graph theory)|stars]] ''K''<sub>1,''k''</sub> are uniquely ''k''-edge-colorable.  Moreover, {{harvtxt|Wilson|1976}} conjectured and {{harvtxt|Thomason|1978}} 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 cycle]]s, 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.{{sfnp|Thomason|1982}}
Every simple [[planar graph|planar]] cubic graph that is uniquely 3-edge-colorable contains a triangle,{{sfnp|Fowler|1998}} but {{harvs|first=W. T.|last=Tutte|year=1976|authorlink=W. T. Tutte|txt}} observed that  the [[generalized Petersen graph]] ''G''(9,2) is [[planar graph|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<ref>{{harvtxt|Bollobás|1978}}; {{harvtxt|Schwenk|1989}}.</ref> but now infinitely many triangle-free non-planar cubic uniquely 3-edge-colorable graphs are known.{{sfnp|belcastro|Haas|2015}}

===Unique total colorability===
A '''uniquely total colorable graph''' is a [[Total coloring|''k''-total-chromatic graph]] that has only one possible [[Total coloring|(proper) ''k''-total-coloring]] up to permutation of the colors.

[[Empty graph]]s, [[Path graph|paths]], and [[Cycle graph|cycles]] of length divisible by 3 are uniquely total colorable graphs.
{{harvtxt|Mahmoodian|Shokrollahi|1995}} conjectured that they are also the only members in this family.

Some properties of a uniquely ''k''-total-colorable graph ''G'' with ''n'' vertices:
# χ″(''G'') = Δ(''G'') + 1 unless ''G'' = ''K''<sub>2</sub>.{{sfnp|Akbari|Behzad|Hajiabolhassan|Mahmoodian|1997}}
# Δ(''G'') ≤ 2 δ(''G'').{{sfnp|Akbari|Behzad|Hajiabolhassan|Mahmoodian|1997}}
# Δ(''G'') ≤ n/2 + 1.{{sfnp|Akbari|2003}}
Here χ″(''G'') is the [[Total coloring|total chromatic number]]; Δ(''G'') is the [[Glossary of graph theory#Degree|maximum degree]]; and δ(''G'') is the [[Glossary of graph theory#Degree|minimum degree]].