[HTML][HTML] Chromatic equivalence classes of complete tripartite graphs

GL Chia, CK Ho - Discrete mathematics, 2009 - Elsevier
Discrete mathematics, 2009Elsevier
Some necessary conditions on a graph which has the same chromatic polynomial as the
complete tripartite graph Km, n, r are developed. Using these, we obtain the chromatic
equivalence classes for Km, n, n (where 1≤ m≤ n) and [Formula: see text](where| mi− mj|≤
3). In particular, it is shown that (i) Km, n, n (where 2≤ m≤ n) and (ii)[Formula: see
text](where| mi− mj|≤ 3, 2≤ mi, i= 1, 2, 3) are uniquely determined by their chromatic
polynomials. The result (i), proved earlier by Liu et al.[RY Liu, HX Zhao, CY Ye, A complete …
Some necessary conditions on a graph which has the same chromatic polynomial as the complete tripartite graph Km,n,r are developed. Using these, we obtain the chromatic equivalence classes for Km,n,n (where 1≤m≤n) and [Formula: see text] (where |mi−mj|≤3). In particular, it is shown that (i) Km,n,n (where 2≤m≤n) and (ii) [Formula: see text] (where |mi−mj|≤3, 2≤mi,i=1,2,3) are uniquely determined by their chromatic polynomials. The result (i), proved earlier by Liu et al. [R.Y. Liu, H.X. Zhao, C.Y. Ye, A complete solution to a conjecture on chromatic uniqueness of complete tripartite graphs, Discrete Math. 289 (2004) 175–179], answers a conjecture (raised in [G.L. Chia, B.H. Goh, K.M. Koh, The chromaticity of some families of complete tripartite graphs (In Honour of Prof. Roberto W. Frucht), Sci. Ser. A (1988) 27–37 (special issue)]) in the affirmative, while result (ii) extends a result of Zou [H.W. Zou, On the chromatic uniqueness of complete tripartite graphs [Formula: see text] J. Systems Sci. Math. Sci. 20 (2000) 181–186].
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果