A Note on Chromatic Uniqueness of Certain Complete Tripartite Graphs

作者：Chen Xiang'en^*; Su Keyi; Yao Bing

来源：Ars Combinatoria, 2012, 105: 205-211.

• Complete tripartite graph
• Chromatic polynomial
• Chromatic uniqueness
• Chromatically unique graph

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 congruent to 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 had given that if n > 1/3(m(2)+k(2)+mk+2 root 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 chi-unique). In this paper, we give that for any positive integers n, m and k, let G = K(n-m, n, n+k), where m >= 2 and k >= 1, if n >= max{inverted right perpendicular1/4m(2) + m + kinverted left perpendicular, inverted right perpendicular1/4m(2) + 3/2m + 2k - 11/4inverted left perpendicular, inverted right perpendicularmk + m - k + 1inverted left perpendicular}, then G is chi-unique. It is an improvement on H.W. Zou's result in the case m >= 2 and k >= 1.

• 出版日期2012-7
• 单位西北师范大学