3—正則3—邊可著色圖的極大擴(kuò)容圖的整數(shù)流

摘 要：研究了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