Schrijver图S_G(2k+2,k)的全色数  

The Total Chromatic Number of Schrijver Graph S_G(2k+2,k)

作　　者：李志江[1] 卢建立[2] 

机构地区：[1]临沂大学沂水分校,山东临沂276400 [2]河南师范大学数学与信息科学学院,河南新乡453007

出　　处：《河北师范大学学报（自然科学版）》2014年第1期6-9,共4页Journal of Hebei Normal University：Natural Science

基　　金：山东省自然科学基金(ZR2009AM013)

摘　　要：图G的一个k-全染色是用k种颜色对图G的顶点和边进行染色,使得任意相邻的边、相邻的顶点和相关联的顶点和边都染不同的颜色.图G的全色数是图G的k-全染色中最小的k值,记为χ″(G).Behzad和Vizing分别独立地提出了著名的全染色猜想TCC:Δ+1≤χ″(G)≤Δ+2,Δ表示图G的最大度.研究了Schrijver图SG(2k+2,k)的全色数问题,得到了χ″(SG(2k+2,k))=Δ+1=k+3,其中k≥2.A k-total coloring of a graph G a proper coloring with k colors such that no adjacent vertices, no adjacent edges, and no edge and its incident vertices are assigned the same color. The total chromatic number Z＇Z（G） of G is the least number k for which G has a k-total coloring. For a simple graph G with max imum degree. Behzad and Vizing independently made the follwing conjeture.△＋1≤x（G）≤△＋2. In this paper,we determine the total chromatic number of Schrijver graph （SG（2k＋2,k））=△＋1=k＋3, where k≥2.

关 键 词：Schrijver图 均衡完全二部图 全色数 圈 路 

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