CLASSIFICATION OF COMPLETE 5-PARTITE GRAPHS AND CHROMATICITY OF 5-PARTITE GRAPHS WITH 5n + 2 VERTICES

Abstract

Let P(G, λ) be the chromatic polynomial of a graph G. Then two graphs G and H are said to be chromatically equivalent, denoted as G ~ H, if P( )( ) G, λ = P H, λ . We write [G] = {H | H ~ G}. If [G] = {G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 5-partite graphs with 2 5n + vertices according to the number of 6-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As