Chromaticity of a family of 5-partite graphs

Abstract EN

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] = {HOEH 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.