Chromaticity of a family of 5-partite graphs

Abstract

Let P(G,k) be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G H, if P(G,k) = P(H,k). 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 G with 5n vertices according to the number of 6-independent partitions of G. Using these results, we investigate the chromaticity of G with certain stars or matching deleted parts . As a by-product, two new families of chromatically unique complete 5-partite graphs G with certain stars or matching deleted parts are obtained