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

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

QR Code Link :
Type :	article
Subject :	QA Mathematics
ISSN :	1735-8515
Main Author :	Abd Karim Nor Suriya, Hasni R., Lau G.C.,
Title :	A new result on chromaticity of k4-homeomorphic graphs with girth 9

Year of Publication :

2017

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.

This material may be protected under Copyright Act which governs the making of photocopies or reproductions of copyrighted materials.
You may use the digitized material for private study, scholarship, or research.

Back to previous page