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.0501-02).
 Author Name Affiliation Ke Yi SU Yinchuan Sixth Middle School, Ningxia 750011, P. R. China College of Mathematics and Information Science, Northwest Normal University, Gansu 730070, P. R. China Xiang En CHEN College of Mathematics and Information Science, Northwest Normal University, Gansu 730070, P. R. China
Hits: 2981
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 Hui-wen 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 non-negative integers, then the complete tripartite graph $K(n-m,n,n k)$ is chromatically unique (or simply $\chi$--unique). In this paper, we prove that for any non-negative 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(n-m,n,n k)$ is $\chi$--unique, which is an improvement on Zou Hui-wen's result in the case $m\geq2$ and $k\geq0.$ Furthermore, we present a related conjecture.