Editing Uniquely colorable graph

{{short description|Graph with only one possible coloring}}

In [[graph theory]], a '''uniquely colorable graph''' is a {{mvar|k}}-chromatic [[Graph (discrete mathematics)|graph]] that has only one possible (proper) {{mvar|k}}-[[Graph coloring|coloring]] up to [[permutation]] of the colors.  Equivalently, there is only one way to [[Graph partition|partition]] its [[Vertex (graph theory)|vertices]] into {{mvar|k}} [[independent set (graph theory)|independent set]]s and there is no way to partition them into {{math|''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|''k''-tree]] is uniquely (''k''&nbsp;+&nbsp;1)-colorable. The uniquely 4-colorable [[planar graph]]s are known to be exactly the [[Apollonian network]]s, that is, the planar 3-trees.{{sfnp|Fowler|1998}}

Every connected [[bipartite graph]] is uniquely 2-colorable. Its 2-coloring can be obtained by choosing a starting vertex arbitrarily, coloring the vertices at even distance from the starting vertex with one color, and coloring the vertices at odd distance from the starting vertex with the other color.{{sfnp|Mahmoodian|1998}}

==Properties==
A uniquely {{mvar|k}}-colorable graph {{mvar|G}} with {{mvar|n}} vertices has at least {{math|''m'' ≥ (''k''−1)''n'' − ''k''(''k''−1)/2}} edges. Equality holds when {{mvar|G}} is a {{math|(''k''−1)}}-tree.<ref>{{harvtxt|Truszczyński|1984}}; {{harvtxt|Xu|1990}}.</ref>

==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]].

==Notes==
{{reflist}}

== References ==
*{{citation
 | last = Akbari | first = S.
 | doi = 10.1016/S0012-365X(02)00797-5
 | issue = 1–3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1991705
 | pages = 41–45
 | title = Two conjectures on uniquely totally colorable graphs
 | volume = 266
 | year = 2003| doi-access = free
 }}.
*{{citation
 | last1 = Akbari | first1 = S.
 | last2 = Behzad | first2 = M.
 | last3 = Hajiabolhassan | first3 = H.
 | last4 = Mahmoodian | first4 = E. S.
 | doi = 10.1016/S0012-365X(02)00797-5
 | issue = 4
 | journal = [[Graphs and Combinatorics]]
 | mr = 1485924
 | pages = 305–314
 | title = Uniquely total colorable graphs
 | volume = 13
 | year = 1997| doi-access = free
 }}.
*{{citation
 | last1 = belcastro | first1 = sarah-marie | author1-link = Sarah-Marie Belcastro
 | last2 = Haas | first2 = Ruth | author2-link = Ruth Haas
 | arxiv = 1508.06934
 | doi = 10.11575/cdm.v10i2.62320 | doi-access = free
 | issue = 2
 | journal = Contributions to Discrete Mathematics
 | mr = 3499076
 | pages = 39–44
 | title = Triangle-free uniquely 3-edge colorable cubic graphs
 | volume = 10
 | year = 2015}}.
*{{citation
 | last = Bollobás | first = Béla | author-link = Béla Bollobás
 | mr = 0506522
 | publisher = Academic Press
 | series = LMS Monographs
 | title = Extremal Graph Theory
 | volume = 11
 | year = 1978}}.
*{{citation|first=Thomas|last=Fowler|url=http://people.math.gatech.edu/~thomas/FC/fowlerphd.pdf|year=1998|title=Unique Coloring of Planar Graphs|series=Ph.D. thesis|publisher=Georgia Institute of Technology Mathematics Department}}.
*{{citation
 | last1 = Hillar | first1 = Christopher J.
 | last2 = Windfeldt | first2 = Troels
 | doi = 10.1016/j.jctb.2007.08.004
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 2389606
 | pages = 400–414
 | series = Series B
 | title = Algebraic characterization of uniquely vertex colorable graphs
 | volume = 98
 | year = 2008| arxiv = math/0606565
 | s2cid = 108304
 }}.
*{{citation
 | last = Mahmoodian | first = E. S.
 | doi = 10.1016/S0378-3758(98)00053-6
 | issue = 1–2
 | journal = Journal of Statistical Planning and Inference
 | mr = 1655213
 | pages = 85–89
 | title = Defining sets and uniqueness in graph colorings: a survey
 | volume = 73
 | year = 1998}}.
*{{citation|last1=Mahmoodian|first1= E. S.|last2= Shokrollahi|first2= M. A.|year=1995|contribution=Open problems at the combinatorics workshop of AIMC25 (Tehran, 1994)|title= Combinatorics Advances|editor1-first=Colbourn|editor1-last= C. J.|editor1-link=Charles Colbourn|editor2-first= Mahmoodian|editor2-last= E. S.|series= Mathematics and its applications|volume=329|pages= 321–324|location=  Dordrecht; Boston; London|publisher= Kluwer Academic Publishers}}.
*{{citation
 | last = Schwenk | first = Allen J.
 | doi = 10.1016/0095-8956(89)90064-6
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 1007713
 | pages = 53–59
 | title = Enumeration of Hamiltonian cycles in certain generalized Petersen graphs
 | volume = 47
 | year = 1989| doi-access = free
 }}.
*{{citation
 | last = Thomason | first = A. G.
 | contribution = Hamiltonian cycles and uniquely edge colourable graphs
 | mr = 499124
 | pages = 259–268
 | series = Annals of Discrete Mathematics
 | title = Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977)
 | volume = 3
 | year = 1978}}.
*{{citation
 | last = Thomason | first = Andrew
 | doi = 10.1002/jgt.3190060218
 | issue = 2
 | journal = Journal of Graph Theory
 | mr = 655209
 | pages = 219–221
 | title = Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable
 | volume = 6
 | year = 1982}}.
*{{citation
 | last = Truszczyński | first = M.
 | editor1-last = Hajnal | editor1-first = A. | editor1-link = András Hajnal
 | editor2-last = Lovász | editor2-first = L. | editor2-link = László Lovász
 | editor3-last = Sós | editor3-first = V. T. | editor3-link = Vera T. Sós
 | contribution = Some results on uniquely colourable graphs
 | mr = 818274
 | pages = 733–748
 | publisher = North-Holland, Amsterdam
 | series = Colloq. Math. Soc. János Bolyai
 | title = Finite and Infinite Sets. Vol. I, II. Proceedings of the sixth Hungarian combinatorial colloquium held in Eger, July 6–11, 1981
 | volume = 37
 | year = 1984}}.
*{{citation
 | last = Tutte | first = William T.
 | contribution = Hamiltonian circuits
 | mr = 0480185
 | pages = 193–199. Atti dei Convegni Lincei, No. 17
 | publisher = Accad. Naz. Lincei, Rome
 | title = Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I
 | year = 1976}}. As cited by {{harvtxt|belcastro|Haas|2015}}.
*{{citation
 | last = Xu | first = Shao Ji
 | doi = 10.1016/0095-8956(90)90086-F
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 1081235
 | pages = 319–320
 | series = Series B
 | title = The size of uniquely colorable graphs
 | volume = 50
 | year = 1990| doi-access = free
 }}.
*{{citation|last=Wilson|first=R. J.|contribution=Problem 2|page=696|title=Proc. British Comb. Conf. 1975|year=1976|editor1-first=C. St. J. A.|editor1-last=Nash-Williams|editor1-link=Crispin Nash-Williams|editor2-first=J.|editor2-last=Sheehan|location=Winnipeg|publisher=Utilitas Math.}}. As cited by {{harvtxt|Thomason|1978}}.

==External links==
*{{mathworld|title=Uniquely Colorable Graph|id=UniquelyColorableGraph|mode=cs2}}

[[Category:Graph coloring]]