Uniquely colorable graph

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors.

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 (k + 1)-colorable. The uniquely 4-colorable planar graphs are known to be exactly the Apollonian networks, that is, the planar 3-trees (Fowler 1998).

Properties

Some properties of a uniquely k-colorable graph G with n vertices and m edges:

1. m ≥ (k - 1) n - k(k-1)/2. (Truszczyński 1981; Xu 1990)

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

The unique 3-edge-coloring of the generalized Petersen graph G(9,2)

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 K_1,k are uniquely k-edge-colorable graphs. Moreover, Wilson (1967) conjectured and 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. The generalized Petersen graph G(9,2) is the only known nonplanar uniquely 3-edge-colorable graph, and it has been conjectured that it is the only such graph. See Bollobás (1978) and Schwenk (1989).

Unique total colorability

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. 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:

1. χ″(G) = Δ(G) + 1 unless G = K₂. (Akbari et al. 1997)
2. Δ(G) ≤ 2 δ(G). (Akbari et al. 1997)
3. Δ(G) ≤ n/2 + 1. (Akbari 2003)

Here χ″(G) is the total chromatic number; Δ(G), maximum degree; and δ(G), minimum degree.

References

• Akbari, S. (2003), "Two conjectures on uniquely totally colorable graphs", Discrete Math. 266 (1–3): 41–45, doi:10.1016/S0012-365X(02)00797-5 .
• Akbari, S.; Behzad, M.; Haijiabolhassen, H.; Mahmoodian (1997), "Uniquely total colorable graphs", Graphs Combin 13: 305–314 .
• Bollobás, Béla (1978). Extremal graph theory, Vol. 11, LMS Monographs. London; New York; San Francisco: Academic Press.
• Fowler, Thomas (1998), Unique Coloring of Planar Graphs, Ph.D. thesis, Georgia Institute of Technology Mathematics Department .
• Hillar, C.; Windfeldt, T. (2008), "An algebraic characterization of uniquely vertex colorable graphs", Journal of Combinatorial Theory, Series B 98 (2): 400–414, doi:10.1016/j.jctb.2007.08.004 .
• Mahmoodian, E. S.; Shokrollahi, M. A. (1995), "Open problems at the combinatorics workshop of AIMC25 (Tehran, 1994)", in C. J., Colbourn; E. S., Mahmoodian, Combinatorics Advances, Mathematics and its applications 329, Dordrecht; Boston; London: Kluwer Academic Publishers, pp. 321–324 .
• Schwenk, Allen J. (1989), "Enumeration of Hamiltonian cycles in certain generalized Petersen graphs", Journal of Combinatorial Theory, Series B 47 (1): 53–59, doi:10.1016/0095-8956(89)90064-6, MR 1007713 .
• Truszczyński, M. (1981), "Some results on uniquely colourable graphs", Soloquia Math. Soc. János Bolyai 37: 733–746 .
• Xu, Shaoji (1990), "The size of uniquely colorable graphs", J. Combin. Theory (B) 50 (2): 319–320, doi:10.1016/0095-8956(90)90086-F .