Uniquely colorable graph
In graph theory, a uniquely colorable graph is a Template:Mvar-chromatic graph that has only one possible (proper) Template:Mvar-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into Template:Mvar independent sets and there is no way to partition them into Template:Math independent sets.
ExamplesEdit
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 (k + 1)-colorable. The uniquely 4-colorable planar graphs are known to be exactly the Apollonian networks, that is, the planar 3-trees.Template:Sfnp
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.Template:Sfnp
PropertiesEdit
A uniquely Template:Mvar-colorable graph Template:Mvar with Template:Mvar vertices has at least Template:Math edges. Equality holds when Template:Mvar is a Template:Math-tree.<ref>Template:Harvtxt; Template:Harvtxt.</ref>
Related conceptsEdit
Minimal imperfectionEdit
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 colorabilityEdit
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. The only uniquely 2-edge-colorable graphs are the paths and the cycles. For any k, the stars K1,k are uniquely k-edge-colorable. Moreover, Template:Harvtxt conjectured and Template:Harvtxt 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.Template:Sfnp Every simple planar cubic graph that is uniquely 3-edge-colorable contains a triangle,Template:Sfnp but Template:Harvs observed that the generalized Petersen graph G(9,2) 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<ref>Template:Harvtxt; Template:Harvtxt.</ref> but now infinitely many triangle-free non-planar cubic uniquely 3-edge-colorable graphs are known.Template:Sfnp
Unique total colorabilityEdit
A uniquely total colorable graph is a k-total-chromatic graph that has only one possible (proper) k-total-coloring up to permutation of the colors.
Empty graphs, paths, and cycles of length divisible by 3 are uniquely total colorable graphs. Template:Harvtxt 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 = K2.Template:Sfnp
- Δ(G) ≤ 2 δ(G).Template:Sfnp
- Δ(G) ≤ n/2 + 1.Template:Sfnp
Here χ″(G) is the total chromatic number; Δ(G) is the maximum degree; and δ(G) is the minimum degree.
NotesEdit
ReferencesEdit
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation. As cited by Template:Harvtxt.
- Template:Citation.
- Template:Citation. As cited by Template:Harvtxt.