摘要
文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。
The chromaticity of complete t-partite graph K(n-k,n-2,n,…,n) is introduced. Let P(G, 2) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H, A)=P(G, /l) implies HG. By comparing the chromatic number of partition into t+1-color classes of the t-partite graph and the number of the triangular subgraph of graphs, it is proved that K(n-k,n-2,n,…,n) is chromatically unique if n〉[(k+1)2/4]+1 and k〉2.
出处
《合肥工业大学学报(自然科学版)》
CAS
CSCD
北大核心
2013年第9期1148-1152,共5页
Journal of Hefei University of Technology:Natural Science
基金
淮南职业技术学院科研资助项目(HKJ10-6)
关键词
色唯一图
色划分数
完全t部图
三角形子图
chromatically unique graph
number of partition into color class
complete t-partite graph
triangular subgraph