Classification of complete 5-partite graphs and chromaticity of 5-partite graphs with 5n vertices

Haixing Zhao, Ruying Liu, Shenggui Zhang

科研成果: 期刊稿件文章同行评审

11 引用 (Scopus)

摘要

For a graph G,P(G,a)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G~H, if P(G,λ) =p(H, λ). Let [G]= {H|H ~G}. If [G]= {G},then G is said tobe chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G) = (α(G, 6) - 2n+l - 2n-1 + 5)/2n-2,where α(G, 6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ (G) = 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these resuhs the chromaticity of 5-partite graphs of the form G-S with θ(G) = 0, 1,2,5/2,7/2,4, 17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained.

源语言英语
页(从-至)116-124
页数9
期刊Applied Mathematics
19
1
DOI
出版状态已出版 - 3月 2004

引用此