Uniquely k-Colorable Graph
المؤلف:
Chao, C.-Y.
المصدر:
"Uniquely N-Colorable and Chromatically Equivalent Graphs." Bull. Malays. Math. Sci. Soc. 24
الجزء والصفحة:
...
1-4-2022
2256
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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
