A new result on chromaticity of K4-homoemorphs with girth 9

Document Type : Research Paper

Authors

1 Department of Mathematics‎, ‎Faculty of Science and Mathematics‎, ‎Universiti Pendidikan Sultan Idris‎, ‎35900 Tanjong Malim‎, ‎Perak‎, ‎Malaysia.

2 School of Informatics and Applied Mathematics‎, ‎University Malaysia Terengganu‎, ‎21030 Kuala Terengganu‎, ‎Terengganu‎, ‎Malaysia.

3 Faculty of Computer and Mathematical Sciences‎, ‎University Teknologi MARA (Segamat Campus) ‎85000 Segamat‎, ‎Johor‎, ‎Malaysia.

Abstract

For a graph $G$, let $P(G,lambda)$ 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 $K_4$-homeomorph is a subdivision of the complete graph $K_4$. In this paper, we determine a family of chromatically unique $K_4$-homeomorphs which have girth 9 and has exactly one path of length 1, and give sufficient and necessary condition for the graphs in this family to be chromatically unique.

Keywords

Main Subjects

References

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

Files

History

  • Receive Date: 24 March 2015
  • Revise Date: 17 November 2015
  • Accept Date: 17 November 2015

Share

How to cite

Statistics