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 \geq 2\) and \(k \geq 1\), if \(n \geq \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 \geq 2\) and \(k \geq 1\).