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.

Example 1. 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.

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)

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.

Example 2. The stars K_1,k are uniquely k-edge-colorable graphs. Moreover, R. J. Wilson (1967) conjectured and A. G. Thomason (1978) proved that, when k ≥ 4, they are also the only members in this family. See [Bollobás 1978].

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.

Example 3. Empty graphs, paths, and cycles of length divisible by 3 are uniquely total colorable graphs. Mahmoodian and 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.
• Akbari, S.; Behzad, M.; Haijiabolhassen, H.; Mahmoodian (1997). Uniquely total colorable graphs. Graphs Combin. 13, 305–314.
• Bollobás, Bela (1978). Extremal graph theory, Vol. 11, LMS Monographs. London; New York; San Francisco: Academic Press.
• Mahmoodian, E. S.; Shokrollahi, M. A. (1995). Open problems at the combinatorics workshop of AIMC25 (Tehran, 1994), in Combinatorics Advances. In Colbourn, C. J.; Mahmoodian, E. S. (Eds.), Mathematics and its applications, 321–324. Dordrecht; Boston; London: Kluwer Academic Publishers.
• 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, 319–320.