CLASSIFICATION OF COMPLETE 5-PARTITE GRAPHS AND CHROMATICITY OF 5-PARTITE GRAPHSWITH 5n VERTICES

For a graph G,P(G,λ)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,λ). LetG]= {H|H-G}. If G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(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 results 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.

Classification of complete 5-partite graphs and chromaticity of 5-partite graphs with 5<Emphasis Type="Italic">n</Emphasis> vertices

For a graph G,P(G,λ)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 to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define ϑ(G)=(α(G,6) − 2 _n−1 − 2 ⁿ⁻¹+5)/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 results 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. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.