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 1984; 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 K1,k are uniquely k-edge-colorable graphs. Moreover, Wilson (1976) 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:
- χ″(G) = Δ(G) + 1 unless G = K2. (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 Mathematics 266 (1-3): 41–45, doi:10.1016/S0012-365X(02)00797-5, MR 1991705.
- Akbari, S.; Behzad, M.; Hajiabolhassan, H.; Mahmoodian, E. S. (1997), "Uniquely total colorable graphs", Graphs and Combinatorics 13 (4): 305–314, doi:10.1016/S0012-365X(02)00797-5, MR 1485924.
- Bollobás, Béla (1978), Extremal Graph Theory, LMS Monographs 11, Academic Press, MR 0506522.
- Fowler, Thomas (1998), Unique Coloring of Planar Graphs (PDF), Ph.D. thesis, Georgia Institute of Technology Mathematics Department.
- Hillar, Christopher J.; Windfeldt, Troels (2008), "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, MR 2389606.
- 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.
- Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics 3, pp. 259–268, MR 499124.
- Truszczyński, M. (1984), "Some results on uniquely colourable graphs", in Hajnal, A.; Lovász, L.; Sós, V. T., Finite and Infinite Sets. Vol. I, II. Proceedings of the sixth Hungarian combinatorial colloquium held in Eger, July 6–11, 1981, Colloq. Math. Soc. János Bolyai 37, North-Holland, Amsterdam, pp. 733–748, MR 818274.
- Xu, Shao Ji (1990), "The size of uniquely colorable graphs", Journal of Combinatorial Theory, Series B 50 (2): 319–320, doi:10.1016/0095-8956(90)90086-F, MR 1081235.
- Wilson, R. J. (1976), "Problem 2", in Nash-Williams, C. St. J. A.; Sheehan, J., Proc. British Comb. Conf. 1975, Winnipeg: Utilitas Math., p. 696. As cited by Thomason (1978).