A new result on chromaticity of k4-homeomorphic graphs with girth 9

Abd Karim Nor Suriya, Hasni R., Lau G.C.,

Full Text

For a graph G, let P(G, λ) denote the chromatic polynomial of G. Two graphs G and H are chromatically equivalent if they share the same chromatic polynomial. A graph G is chromatically unique if any graph chromatically equivalent to G is isomorphic to G. A K4- homeomorph is a subdivision of the complete graph K4. In this paper,we determine a family of chromatically unique K4-homeomorphs which have girth 9 and have exactly one path of length 1,and give sufficient and necessary condition for the graphs in this family to be chromatically unique.

References

[1] S. Catada-Ghimire and R. Hasni, New result on chromaticity of K4-homeomorphic graphs, Int. J. Comput. Math. 91 (2014), no. 5, 834–843. [2] S. Catada-Ghimire, R. Hasni and Y.H. Peng, Chromatically equivalent pairs of K4-homeomorphic graphs, Acta Math. Appl. Sin. Engl. Ser. 2010 (2010) DOI: 10.1007/s10255-010-0034-x, 8 pages. [3] C.Y. Chao and L.C. Zhao, Chromatic polynomials of a family of graphs, Ars Combin. 15 (1983) 111–129. [4] X.E. Chen and K.Z. Ouyang, Chromatic classes of certain 2-connected (n,n+2)-graphs homeomorphs to K4, Discrete Math. 172 (1997), no. 1-3, 17–29. [5] F.M. Dong, K.M. Koh and K.L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific Publishing, Hackensack, NJ, 2005. [6] Z.Y. Guo and E.G. Whitehead Jr., Chromaticity of a family of K4-homeomorphs, Discrete Math. 172 (1997), no. 1-3, 53–58. [7] R. Hasni, Chromatic equivalence of a family of K4-homeomorphs with girth 9, Int. J.Pure Appl. Math. 85 (2013), no. 1, 33–43. [8] N.S.A. Karim, R. Hasni and G.C. Lau, Chromaticity of a family of K4-homeomorphs with girth 9, AIP Conf. Proc. 1605 (2014) 563–567. [9] N.S.A. Karim, R. Hasni and G.C. Lau, Chromaticity of a family of K4-homeomorphs with girth 9 II, Malays. J. Math. Sci. 9 (2015), no. 3, 367–396. [10] K.M. Koh and K.L. Teo, The search for chromatically unique graphs, Graphs Combin. 6 (1990), no. 3, 259–285. [11] K.M. Koh and K.L. Teo, The search for chromatically unique graphs, II, Discrete Math.172(1997),no.1-3, 59–78. [12] W.M. Li, Almost every K4-homeomorphs is chromatically unique, Ars Combin. 23 (1987) 13–35. [13] Y.L. Peng, Some new results on chromatic uniqueness of K4-homeomorphs, Discrete Math. 228 (2004), no. 1-3, 177–183. [14] Y.L. Peng, Chromatic uniqueness of a family of K4-homeomorphs, Discrete Math. 308 (2008), no. 24, 6132–6140. [15] Y.L. Peng, A family of chromatically unique K4-homeomorphs, Ars Combin. 105 (2012) 491–502. [16] Y.L. Peng and R.Y. Liu, Chromaticity of a family of K4-homeomorphs, Discrete Math.258 (2002),no. 1-3,161–177. [17] H.Z. Ren, On the chromaticity of K4 homeomorphs, Discrete Math. 252 (2002), no. 1-3, 247–257. [18] W. Shi, On the Critical Group and Chromatic Uniqueness of a Graph, Master Thesis, University of Science and Technology of China, P.R. China, 2011. [19] W. Shi, Y.I. Pan and Y. Zhao, Chromatic uniqueness of K4-homeomorphs with girth 8, J. Math. Res. Appl. 32 (2012), no. 3, 269–280. [20] E.G. Whitehead Jr. and L.C. Zhao, Chromatic uniqueness and equivalence of K4 homeomorphs, J. Graph Theory 8 (1984), no. 3, 355–364. [21] S. Xu, A lemma in studying chromaticity, Ars Combin. 32 (1991) 315–318. [22] S. Xu, Chromaticity of a family of K4-homeomorphs, Discrete Math. 117 (1993), no.1-3, 293–297.