TY - JOUR
T1 - Classification of complete 5-partite graphs and chromaticity of 5-partite graphs with 5n vertices
AU - Zhao, Haixing
AU - Liu, Ruying
AU - Zhang, Shenggui
N1 - Publisher Copyright:
© 2004, Springer Verlag. All rights reserved.
PY - 2004/3
Y1 - 2004/3
N2 - 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.
AB - 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.
KW - Chromatic uniqueness
KW - Ehromatic polynomial
KW - χ-closed
UR - http://www.scopus.com/inward/record.url?scp=84979071607&partnerID=8YFLogxK
U2 - 10.1007/s11766-004-0029-6
DO - 10.1007/s11766-004-0029-6
M3 - 文章
AN - SCOPUS:84979071607
SN - 1005-1031
VL - 19
SP - 116
EP - 124
JO - Applied Mathematics
JF - Applied Mathematics
IS - 1
ER -