A Note on Chromatic Uniqueness of Completely Tripartite Graphs 
Received:January 14, 2008 Revised:July 07, 2008 
Key Words:
complete tripartite graph chromatic polynomial chromatic uniqueness color partition.

Fund Project:Supported by the National Natural Science Foundation of China (Grant No.10771091) and the Science and Research Project of the Education Department of Gansu Province (Grant No.050102). 

Hits: 2981 
Download times: 2417 
Abstract: 
Let $P(G,\lambda)$ be the chromatic polynomial of a simple graph $G.$ A graph $G$ is chromatically unique if for any simple graph $H,$ $P(H,\lambda)=P(G,\lambda)$ implies that $H$ is isomorphic to $G$. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Huiwen showed that if $n>\frac{1}{3}m^{2} \frac{1}{3}k^{2} \frac{1}{3}mk \frac{1}{3}m\frac{1}{3}k \frac{2}{3} \sqrt{m^{2} k^{2} mk}$, where $n,k$ and $m$ are nonnegative integers, then the complete tripartite graph $K(nm,n,n k)$ is chromatically unique (or simply $\chi$unique). In this paper, we prove that for any nonnegative integers $n, m$ and $k,$ where $m\geq2$ and $k\geq0,$ if $n\geq\frac{1}{3}m^{2} \frac{1}{3}k^{2} \frac{1}{3}mk \frac{1}{3}m\frac{1}{3}k \frac{4}{3}$, then the complete tripartite graph $K(nm,n,n k)$ is $\chi$unique, which is an improvement on Zou Huiwen's result in the case $m\geq2$ and $k\geq0.$ Furthermore, we present a related conjecture. 
Citation: 
DOI:10.3770/j.issn:1000341X.2010.02.005 
View Full Text View/Add Comment Download reader 


