A Note on Chromatic Uniqueness of Completely Tripartite Graphs
Received:January 14, 2008  Revised:July 07, 2008
Key Word: complete tripartite graph   chromatic polynomial   chromatic uniqueness   color partition.  
Fund ProjectL: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 NameAffiliation
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: 2417
Download times: 2026
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 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.
Citation:
DOI:10.3770/j.issn:1000-341X.2010.02.005
View Full Text  View/Add Comment  Download reader