On Chromaticity of Wheels

Authors: Zainab Yasir Al-Rekaby, Abdul Jalil M. Khalaf

Abstract:

Let the vertices of a graph such that every two adjacent vertices have different color is a very common problem in the graph theory. This is known as proper coloring of graphs. The possible number of different proper colorings on a graph with a given number of colors can be represented by a function called the chromatic polynomial. Two graphs G and H are said to be chromatically equivalent, if they share the same chromatic polynomial. A Graph G is chromatically unique, if G is isomorphic to H for any graph H such that G is chromatically equivalent to H. The study of chromatically equivalent and chromatically unique problems is called chromaticity. This paper shows that a wheel W12 is chromatically unique.

Keywords: Chromatic Polynomial, Chromatically Equivalent, Chromatically Unique, Wheel.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1337457

References:

[1] G. D. Birkhoff (1912), A determinate formula for the number of ways of coloring a map, Annal. Math. 14, no. 2, 42-46.
[2] R.C. Read, A note on the chromatic uniqueness of W10, Discrete Math. 69 (1988), 317.
[3] C.Y. Chao and E.G. Whitehead Jr., Chromatically unique graphs, Discrete Math. 27 (1979), 171-177.
[4] G.Chartrand and P.Zahang, chromatic graph theory, Taylor and Francis Graph , LLC. USA(2009).
[5] S.J. Xu and N.Z. Li, The chromaticity of wheels, Dis (1984) 207-212.
[6] N.Z. Li and E.G. Whitehead Jr. The chromatic uniqueness of Discrete Math. 104 (1992), 197-199.
[7] K.M. Koh and K.L. Teo, The search for chromatically unique graphs Discrete Math. 172 (1997), 59-78 .
[8] Farrel, E.J. On chromatic coefficients. Discrete Math. 29, 257 (1980).