UPSI Digital Repository (UDRep)



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 K4homeomorphs 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. CatadaGhimire and R. Hasni, New result on chromaticity of K4homeomorphic graphs, Int. J. Comput. Math. 91 (2014), no. 5, 834–843.
[2] S. CatadaGhimire, R. Hasni and Y.H. Peng, Chromatically equivalent pairs of K4homeomorphic graphs, Acta Math. Appl. Sin. Engl. Ser. 2010 (2010) DOI:
10.1007/s102550100034x, 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 2connected (n,n+2)graphs homeomorphs to K4, Discrete Math. 172 (1997), no. 13, 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 K4homeomorphs, Discrete Math. 172 (1997), no. 13, 53–58.
[7] R. Hasni, Chromatic equivalence of a family of K4homeomorphs 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 K4homeomorphs 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 K4homeomorphs 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.13, 59–78.
[12] W.M. Li, Almost every K4homeomorphs is chromatically unique, Ars Combin. 23 (1987) 13–35.
[13] Y.L. Peng, Some new results on chromatic uniqueness of K4homeomorphs, Discrete Math. 228 (2004), no. 13, 177–183.
[14] Y.L. Peng, Chromatic uniqueness of a family of K4homeomorphs, Discrete Math. 308 (2008), no. 24, 6132–6140.
[15] Y.L. Peng, A family of chromatically unique K4homeomorphs, Ars Combin. 105 (2012) 491–502.
[16] Y.L. Peng and R.Y. Liu, Chromaticity of a family of K4homeomorphs, Discrete Math.258 (2002),no. 13,161–177.
[17] H.Z. Ren, On the chromaticity of K4 homeomorphs, Discrete Math. 252 (2002), no. 13, 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 K4homeomorphs 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 K4homeomorphs, Discrete Math. 117 (1993), no.13, 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. 