摘 要:研究了3-正則3-邊可著色圖的無限擴(kuò)容圖的邊色數(shù),并獲得Tutte的4-流猜想成立的無限類。
關(guān)鍵詞:擴(kuò)容圖; 極大擴(kuò)容圖; k-流; k-邊可著色的; 匹配; k-正則圖
中圖分類號(hào):O243 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1006-3315(2012)12-160-003
1.引言
對(duì)變換圖研究有許多成果,在所有圖的變換中由Whitney給出的線圖,是研究最廣泛的一種變換,產(chǎn)生了豐富的研究成果[1]。擴(kuò)容圖理論是阿勇嘎教授于2009年在文[2]中首次提出的,擴(kuò)容圖是線圖的又一個(gè)推廣,一個(gè)圖的剖分圖的線圖是這個(gè)圖的極大擴(kuò)容圖。圖的擴(kuò)容方法,對(duì)擴(kuò)充圖的容量,而不增加密度很有效且結(jié)構(gòu)簡單。在文[2]中阿勇嘎教授對(duì)擴(kuò)容圖及其譜的一些性質(zhì)進(jìn)行了討論,然而關(guān)于擴(kuò)容圖的整數(shù)流的研究以及其它相關(guān)內(nèi)容至今還沒有更多的討論,即擴(kuò)容圖的研究工作剛剛起步,有著較寬的研究。
1878年,Tait證明了2-邊連通3-正則平面圖是3-可著色的當(dāng)且僅當(dāng)它是4-面可著色的。該結(jié)論將平面圖中的面著色和邊著色聯(lián)系起來,激發(fā)了人們從另一個(gè)角度研究四色定理的興趣。1954年Tutte證明了一個(gè)平面無橋圖是k-面可著色的當(dāng)且僅當(dāng)它有一個(gè)k-流,促進(jìn)了四色定理的研究。文[3]提到Tutte的著名猜想:Tutte-3流、Tutte-4流、Tutte-5流猜想,人們圍繞這些問題展開了很多研究,至今上述猜想還未被攻破,因此,研究猜想成立的圖類很有必要。因而,對(duì)于圖的擴(kuò)容變換下獲得的新圖類,研究Tutte猜想很有意義。
參考文獻(xiàn):
[1]H.Whitney,Congruent graphs and connectivity of graphs. Amer.J.Math,1932.54:p.19
[2]阿勇嘎,斯欽.擴(kuò)容圖及其譜性質(zhì),寶雞文理學(xué)院學(xué)報(bào),2009. 29(1):p.4
[3]Douglas B.West,ed.圖論導(dǎo)引,2006,機(jī)械工業(yè)出版社
[4]徐明曜,ed.有限群導(dǎo)引.1999,科學(xué)出版社
[5]Murty U.S.R Bondy J.A.Graph Theory with Applications.1976:The Macmillan Press LTD