TOPICS
Search

Uniquely Colorable Graph


A uniquely k-colorable graph G is a graph with chromatic number k such that every k-coloring gives the same partition of the vertices of G (Cartwright and Harary 1968; Harary et al. 1969; Ballobás 1978; Harary 1994, pp. 137-140; Chao 2001; Brešar et al. 2023). Equivalently, a graph with chromatic number k is uniquely colorable iff its vertices can be partitioned into k independent vertex sets in exactly one way. It is important to note that this definition does not take the action of a graph automorphism group into account when considering uniqueness, so any symmetries in the graph itself are ignored (i.e., the vertices are considered "fixed").

Examples of uniquely colorable classes of graphs include complete graphs K_n, connected bipartite graphs, n-partite graphs, and trees. k-trees are (k+1)-uniquely colorable (Xu 1990).

The empty graphs K^__n (for n>1) are the only disconnected graphs that are uniquely colorable.

Chartrand and Geller (1969) proved that there are no uniquely 5-colorable planar graphs, and Fowler (1998) characterized uniquely 4-colorable planar graphs as exactly the planar 3-trees (cf. Brešar et al. 2023, who omit the "planar" restriction on 3-trees).

UniquelyColorableGraphs

The numbers of simple uniquely colorable graphs on n=1, 2, ... nodes are 1, 2, 3, 6, 11, 35, 134, 1183, 21319, ... (OEIS A369223).

Uniquely k-colorable graphs are (k-1)-connected (Chartrand and Geller 1969).

Uniquely k-colorable graphs satisfy

 delta>=k-1,
(1)

where delta is the minimum vertex degree (Brešar et al. 2023).

Ballobás (1978) showed that a sufficient condition for a graph G on n vertices and m edges to be uniquely k-colorable is that the inequality

 delta>(3k-5)/(3k-2)n,
(2)

hold. The condition is however not necessary, i.e., there exist graphs that are uniquely colorable but for which the inequality fails to hold.

Truszczyński (1984) and Xu (1990) gave a necessary condition for unique colorability as satisfaction of the inequality

 m>=(k-1)n-1/2k(k-1).
(3)

A graph is therefore not uniquely colorable if the inequality fails to hold, while a graph may or may not be uniquely colorable if it does hold.

Chao (2001) proved that there exist uniquely k-colorable graphs with 2k and 2k+1 vertices for every integer k>=3, and that there exist two uniquely (k+1)-colorable graphs 2k+2 and 2k+3 vertices that are chromatically equivalent.

NonThree-ColorableGraphs

Harary et al. (1969) and Harary (1994, cover and p. 139) gave two graphs that were incorrectly identified as uniquely colorable (as can be seen by the existence of distinct partitions of vertices by color in the illustrations above). The first was corrected in Harary et al. (1970) through the addition of edges on the left, top, and right.

A different definition of unique colorability considers two colorings to be equivalent if there exists a composition of graph automorphism and color exchange that transforms one coloring into the other (Osterweil 1974, Chia 1996, Brešar et al. 2023). To distinguish this case from the more usual definition in which the action of the graph automorphism group has been dropped, Chia (1996) uses the term "uniquely colorable under the action of the automorphism group," while Brešar et al. (2023) term such graphs k-iso-unique. Some graphs may be uniquely colorable under the action of their automorphism group based on the symmetry of the graph alone, i.e., the graph automorphism group itself acts to exchange colors in all possible ways without the need to take color exchange into account explicitly. Examples include the Sierpiński gasket graphs and their generalizations to odd dimensions (D. Knuth, pers. comm., May 1, 2022).


See also

Bipartite Graph, Chromatic Number, Three-Colorable Graph, Vertex Coloring

Explore with Wolfram|Alpha

References

Ballobás, B. "Uniquely Colorable Graphs" J. Combin. Th. 25, 54-61, 1978.Brešar, B.; Dravec, T.; Kleszcz, E. "Uniquely Colorable Graphs Up to Automorphisms." Appl. Math. Comput. 450, 128007, 2023.Cartwright, D. and Harary, F. "On the Coloring of Signed Graphs." Elem. Math. 23, 85-89, 1968.Chao, C.-Y. "Uniquely N-Colorable and Chromatically Equivalent Graphs." Bull. Malays. Math. Sci. Soc. 24, 3-103, 2001.Chao, C.-Y. and Chen, Z. "On Uniquely 3-Colorable Graphs." Disc. Math. 112, 21-27, 1993.Chartrand, G. and Geller, D. P. "On Uniquely Colorable Planar Graphs." J. Combin. Th. 6, 271-278, 1969.Chia, G. L. "On Graphs Uniquely Colorable under the Action of Their Automorphism Groups." Disc. Math. 162, 281-284, 1996.Fowler, T. "Unique Coloring of Planar Graphs." Ph. D. thesis. Athens, GA: Georgia Institute of Technology, 1998.Harary, F. "Uniquely Colorable Graphs." Graph Theory. Reading, MA: Addison-Wesley, pp. 137-140, 1994.Harary, F.; Hedetniemi, S.; and Robinson, R. "Uniquely Colorable Graphs." J. Combin. Th. 6, 264-270, 1969.Harary, F.; Hedetniemi, S.; and Robinson, R. "Erratum to 'Uniquely Colorable Graphs'." J. Combin. Th. 9, 221, 1970.Mahmoodian, E. S. "Defining Sets and Uniqueness in Graph Colorings: A Survey." J. Statistical Planning and Inference 73, 85-89, 1998.Osterweil, L. J. "Some Classes of Uniquely 3-Colorable Graphs." Disc. Math. 8, 59-69, 1974.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Sloane, N. J. A. Sequences A369223 and A369227 in "The On-Line Encyclopedia of Integer Sequences."Truszczyński, M. "Some Results on Uniquely Colourable Graphs." In 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 (Ed. A. Hajnal, L. Lovász, and V. T. Sós). Amsterdam, Netherlands: North-Holland, pp. 733-748, 1984.Xu, S. J. "The Size of Uniquely Colorable Graphs." J. Combin. Th. 50, 319-320, 1990.

Cite this as:

Weisstein, Eric W. "Uniquely Colorable Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UniquelyColorableGraph.html

Subject classifications