具有较大四独立集的色唯一的三部图  

Some chromatically unique tripartite graphs with large 4-independent number

作　　者：尹君[1,2,3] 马秀娟 YIN Jun;MA Xiu-juan(School of Computer Science,Qinghai Normal University,Xining 810016,China;Key Laboratory of Tibetan In formation Processing and Machine Translation,Qinghai Province,Xining 810008,China;Key Laboratory of Tibetan Information Processing,Ministry of Education,Xining 810008,China)

机构地区：[1]青海师范大学计算机学院,青海西宁810016 [2]青海省藏文信息处理与机器翻译重点实验室,青海西宁810008 [3]藏文信息处理教育部重点实验室,青海西宁810008

出　　处：《青海师范大学学报（自然科学版）》2019年第2期1-6,共6页Journal of Qinghai Normal University(Natural Science Edition)

基　　金：青海省自然科学基金(Nos.2017-ZJ-949Q,2019-ZJ-7012);国家自然科学基金(Nos.11801296,61603206)

摘　　要：设G是简单图,G表示图G的补图,用P(G,λ)表示图G的色多项式.若P(G,λ)=P(H,λ),则称G与H是色等价的,简记为H^G.令[G]={H|H^G}.若[G]={G},称G是色唯一的.设Kn,n,n是一个完全三部图且各部分顶点数均为n.图G=Kn,n,n-S表示从完全三部图Kn,n,n中删去边集S所得的图.本文证明了一些具有较大四独立集的三部图是色唯一的.For any graph G,we denote by G the complement and by P(G,λ)the chromatic polynomial of G.Two graphs G and H are said to be equivalent,simply denoted by G^H,if P(G,λ)=P(H,λ).Let[G]={H|H^G}.G is said to be chromatically unique if[G]={G}.Let K n,n,n be a complete tripartite graph and S be a set of some s edges in K n,n,n.Denote by G=K n,n,n-S the graph obtained from K n,n,n by deleting all edges in S.In this paper,we give some chromatically unique tripartite graphds with large 4-independent number.

关 键 词：色多项式 色唯一性 三部图 

分 类 号：O157.5[理学—数学]