設(shè)d1,d2,…,dk為k個非負(fù)整數(shù)。如果可以將圖G的頂點集V劃分為c個子集V1,V2,...,使得對于任意的i=1,2,…,k,Vi的點導(dǎo)出子圖G[Vi]叫的最大度數(shù)至多為di,則稱圖G是（d1,d2,...,4）-可著色的。在2006年,Nsk’s猜想提出,每一個不含3-圈與3-圈相鄰或不含3-圈與5-圈相鄰的平面圖都是3-可著色的。Borodin,Glebov,Raspaud 和 Salavatipour（2005）提出是否每個不含相鄰圈長至多為5的平面圖是3-可著色的?Cohen-Addad（2017）等人在文獻(xiàn)[9]中指出,Nsk’s猜想和Borodin等提出的的問題都是錯誤的。由于這個發(fā)現(xiàn),Zhang,wang和Chen（2016）又提出了是否每個不含相鄰圈長至多為5的平面圖是（1,0,0）-可著色的?基于這個問題,Zhang,wang和Chen證明了不含相鄰圈長至多為5的平面圖是（1,1,0）-可著色的。在本文中,我們證明了每個不含相鄰圈長至多為5的平面圖是（2,0,0）-可著色的。 

【文章來源】：華中師范大學(xué)湖北省 211工程院校 教育部直屬院校

【文章頁數(shù)】：41 頁

【學(xué)位級別】：碩士

【圖文】：

圖２．１圖Ｇ中的壞圈??３??

【參考文獻(xiàn)】：
期刊論文
[1]既不含4-圈又不含6-圈的平面圖的非正常染色[J]. 徐靈姬,王應(yīng)前.  中國科學(xué):數(shù)學(xué). 2013(01)



本文編號：3293689