Uniquely k-Colorable Graph

A uniquely -colorable graph  is a -colorable graph such that every -coloring gives the same partition of  (Chao 2001).

Chao (2001) proved that there exist uniquely -colorable graphs with  and  vertices for every integer , and that there exit two uniquely -colorable graphs  and  vertices that are chromatically equivalent.

The graph illustrated above is a 12-vertex 22-edge triangle-free graph that is three-colorable in exactly one way modulo permutations of colors (Harary et al. 1970). It is implemented in the Wolfram Language as GraphData["UniquelyThreeColorableGraph"], replacing the incorrect graph from Harary (1994, cover and p. 139).

Unfortunately, Harary et al. (1969; left bottom figure) and Harary (1994, p. 139; top and bottom right figures) give not just one but two incorrect versions of this graph. Neither of these is uniquely three-colorable, as can be seen by noting that in the left graph, the lower right-hand green vertex can be replaced with blue, whereas in the right graph, the lower left-hand red vertex can be replaced with blue.

Osterweil (1974) and Chao and Chen (1993) gave families of uniquely 3-colorable graphs without and with triangles, respectively.

REFERENCES

Chao, C.-Y. "Uniquely -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.

Chia, G. L. "On Graphs Uniquely Colorable under the Action of Their Automorphism Groups." Disc. Math. 162, 281-284, 1996.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Harary, F.; Hedetniemi, S.; and Robinson, R. "Erratum to 'Uniquely Colorable Graphs'." J. Combin. Th. 9, 221, 1970.

Harary, F.; Hedetniemi, S.; and Robinson, R. "Uniquely Colorable Graphs." J. Combin. Th. 6, 264-270, 1969.

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.