On the chromaticity of 5-partite graphs with 5n+4 vertices
Haixing Zhao · Journal of Lanzhou University · 2004
Let G be a simple graph, P(G, λ) denote the chromatic polynomial of G, two graphs G and H are said to be chromatically equivalent (or simply by H - G) if P(G, λ) = P(H, λ). We write [G] = {H|H - G}. If [G] = {G}, then G is regarded as chromatically unique. Let G be a complete 5-partite graph with 5n + 4 vertices, we define θ(G) = (m6(G) - 2(N+2) - 2(N-1) + 5)/2(N-1). In this paper, we show that θ(G) ≥ 0 and all graphs are characterized with θ(G) = 0,1,3/2,2,5/2,13/4. Using these results, we investigate the chromaticity of G - S, where S is a set of the edges of G and G - S denotes the graph obtained from G by deleting all the edges in S. Moreover, many new chromatically unique 5-partite graphs have been obtained.