在线阅读 --自然科学版 2014年1期《Schrijver图SG(2k+2,k)的全色数》
Schrijver图SG(2k+2,k)的全色数--[在线阅读]
李志江1, 卢建立2
1. 临沂大学 沂水分校, 山东 临沂 276400;
2. 河南师范大学 数学与信息科学学院, 河南 新乡 453007
起止页码: 6--9页
DOI: 10.11826/j.issn.1000-5854.2014.01.002
摘要
G的一个k全染色是用k种颜色对图G的顶点和边进行染色,使得任意相邻的边、相邻的顶点和相关联的顶点和边都染不同的颜色.图G的全色数是图Gk全染色中最小的k值,记为χ"(G).Behzad和Vizing分别独立地提出了著名的全染色猜想TCC:Δ+1≤χ"(G)≤Δ+2,Δ表示图G的最大度.研究了Schrijver图SG(2k+2,k)的全色数问题,得到了χ"(SG(2k+2,k))=Δ+1=k+3,其中k≥2.

The Total Chromatic Number of Schrijver Graph SG(2k+2,k)
LI Zhijiang1, LU Jianli2
1. Yishui College, Linyi University, Shandong Linyi 276400, China;
2. College of Mathematics and Information Sciences, Henan Normal University, He'nan Xinxiang 453007, China
Abstract:
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 χ"(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≤χ"(G)≤Δ+2.In this paper, we determine the total chromatic number of Schrijver graph S(2k+2, k)χ"(SG(2k+2, k))=Δ+1=k+3, where k≥2.

收稿日期: 2012-12-15
基金项目: 山东省自然科学基金(ZR2009AM013)

参考文献:
[1]BEHZAD M.Graphs and Their Chromatic Numbers [J].P H Docotoral Thesis,1965,2(3):295-300.
[2]VIZING V.Some Unsolved Problems in Graph Theory [J].Uspekhi Mat Nauk,1968,23:117-134.
[3]SHAREBAF S R.Vertex Edge and Total Coloring in Spider Graphs [J].Appl Math Sci,2009,18:877-881.
[4]YORGANCIOGLU Z.Total Coloring of Certain Double Vertex Graphs [J].Appl Math Sci,2011(5):2271-2275.
[5]王江,阿勇噶.扩容图及其染色 [J].内蒙古师范大学学报:自然科学版,2011,40:228-231.
[6]强会英,李沐春,晁福刚,等.完全二部图的广义Mycielski图的全染色与边染色 [J].数学的实践与认识,2007,37:138-142.
[7]沈岚,王应前.最大度至少为8的可平面图的全染色 [J].中国科学A,2008,38:1356-1364.
[8]KNESER M.Aufgabe 300 [J].Jahresber Deutsch Math-Verein,1955,58:27.
[9]LAOVSZ L.Kneser's Conjecture Chromatic Numer and Homotopy [J].Combin Theory Ser A,1978,25:319-324.
[10]SCHRIJVER A.Vertex-critical Subgraphs of Kneser Graph [J].Nienw Arch Wisk(3),1978,26:454-461.
[11]CHEN J Y,LIH K W,WU J J.Coloring the Square of the Kneser Graph KG(2k+1) and the Schrijver Graph SG(2k+2,k) [J].Discrete Applied Mathematics,2009,157:170-176.
[12]XUE B,ZUO L.The Linear Arboricity of the Schrijver Graph SG(2k+2,k) [J].Bull Malays Math Sci Soc,2012,35:239-246.
[13]BONDY J A,MURTY U.Graph Theory with Applications [M].London:Mcmillam Press Ltd,1976.