IJPAM: Volume 81, No. 2 (2012)


R. Hasni$^1$, A. Ahmad$^3$, F. Mustapha$^3$
$^1$Department of Mathematics
Faculty of Science and Technology
University Malaysia Terengganu
21030, Kuala Terengganu, Terengganu, MALAYSIA
$^2$School of Mathematical Sciences
Universiti Sains Malaysia
11800, USM Penang, MALAYSIA

Abstract. For a graph $G$, let $P(G,\lambda)$ denote the chromatic polynomial of $G$. Two graphs $G$ and $H$ are chromatically equivalent (or simply $\chi-$equivalent), denoted by $G\sim H$, if $P(G,\l)=P(H,\l)$. A graph $G$ is chromatically unique (or simply $\chi-$unique) if for any graph $H$ such as $H\sim G$, we have $H\cong G$, i.e, $H$ is isomorphic to $G$. A $K_4$-homeomorph is a subdivision of the complete graph $K_4$. In this paper, we discuss a pair of chromatically equivalent of $K_4$-homeomorphs with girth 9, that is, $K_4(1,3,5,d,e,f)$ and $K_4(1,3,5,d^{\prime},e^{\prime},f^{\prime})$. As a result, we obtain two infinite chromatically equivalent non-isomorphic $K_4$-homeomorphs.

Received: July 6, 2012

AMS Subject Classification: 05C15

Key Words and Phrases: chromatic polynomial, chromatic equivalence, $K_4$-homeomorphs

Download paper from here.

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2012
Volume: 81
Issue: 2