A Note on Chromatic Uniqueness of Certain Complete Tripartite Graphs

Abstract

Let $P(G,\lambda )$ be the chromatic polynomial of a graph $G$. A graph $G$ is chromatically unique if for any graph $H$, $P(H,\lambda )=P(G,\lambda )$ implies $H\cong G$. Some sufficient conditions guaranteeing that certain complete tripartite graph $K(l,n,r)$ is chromatically unique were obtained by many scholars. Especially, in 2003, H.W. Zou showed that if $n>\frac{1}{3}(m^2+k^2+mk+2\sqrt{m^2+k^2+mk}+m–k)$, where $n,k$, and $m$ are non-negative integers, then $K(n–m,n,n+k)$ is chromatically unique (or simply $\lambda$-unique). In this paper, we show that for any positive integers $n,m$, and $k$, let $G=K(n–m,n,n+k)$, where $m\ge 2$ and $k\ge 1$, if $n\ge max\{\lceil \frac{1}{4}{m}^2+m+k\rceil ,\lceil \frac{1}{4}{m}^2+\frac{3}{2}m+2k–\frac{11}{4}\rceil ,\lceil mk+m–k+1\rceil \}$, then $G$ is $\chi$-unique. This improves upon H.W. Zou’s result in the case $m\ge 2$ and $k\ge 1$.