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:

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

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

the unique colourable grphy is fully copyied for kromotogrphy graph

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:

χ″(G) = Δ(G) + 1 unless G = K₂. (Akbari et al. 1997)
Δ(G) ≤ 2 δ(G). (Akbari et al. 1997)
Δ(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 (PDF), 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 (eds.), Combinatorics Advances, Mathematics and its applications, vol. 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.