具有5n+4个点的5部图的色性

On the chromaticity of 5-partite graphs with 5n+4 vertices

设G是简单图,用P(G,λ)表示图G的色多项式,若P(G,λ)=P(H,λ),则称G与H是色等价令H-G,令[G]={H|H-G},若对任意的图G有[G]={G},称G是色唯一的.设G表示具有5n+4个点的完全5部图,令θ(G)=(m6(G)-2(n+2)-2(n-1)+5)/2(n-1),其中m6(G)表示G的6-独立分划个数.本文证明了θ(G)≥0且刻划θ(G)=0,1,3/2,2,5/2,13/4的图.利用此结果研究了图G-S的色性,其中S是图G某些边组成的集合,G-S表示从G中删去S中所有的边得到的图,进而得到许多色唯一的5部图.

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.