关于完全三部图色唯一性的一个注记

Let P(G,λ) be the chromatic polynomial of a simple graph G. A graph G is chromatically unique if for any simple graph H, P(H,λ) = P(G,λ) 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 31m2 + 31k2 + 31mk+ 31m? 31k+ 32√m2 + k2 + 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 χ-unique). In this paper, we prove that for any non-negative integers n,m and k, where m ≥ 2 and k ≥ 0, if n ≥ 31m2 + 31k2 + 31mk + 31m - 31k + 43, then the complete tripartite graph K(n - m,n,n + k) is χ-unique, which is an improvement on Zou Hui-wen's result in the case m ≥ 2 and k ≥ 0. Furthermore, we present a related conjecture.

A Note on Chromatic Uniqueness of Completely Tripartite Graphs

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.