3—正則3—邊可著色圖的極大擴容圖的整數流

摘 要：研究了3-正則3-邊可著色圖的無限擴容圖的邊色數，并獲得Tutte的4-流猜想成立的無限類。

關鍵詞：擴容圖； 極大擴容圖； k-流； k-邊可著色的； 匹配； k-正則圖

中圖分類號：O243 文獻標識碼：A 文章編號：1006-3315（2012）12-160-003

1.引言

對變換圖研究有許多成果，在所有圖的變換中由Whitney給出的線圖，是研究最廣泛的一種變換，產生了豐富的研究成果[1]。擴容圖理論是阿勇嘎教授于2009年在文[2]中首次提出的，擴容圖是線圖的又一個推廣，一個圖的剖分圖的線圖是這個圖的極大擴容圖。圖的擴容方法，對擴充圖的容量，而不增加密度很有效且結構簡單。在文[2]中阿勇嘎教授對擴容圖及其譜的一些性質進行了討論，然而關于擴容圖的整數流的研究以及其它相關內容至今還沒有更多的討論，即擴容圖的研究工作剛剛起步，有著較寬的研究。

1878年，Tait證明了2-邊連通3-正則平面圖是3-可著色的當且僅當它是4-面可著色的。該結論將平面圖中的面著色和邊著色聯系起來，激發了人們從另一個角度研究四色定理的興趣。1954年Tutte證明了一個平面無橋圖是k-面可著色的當且僅當它有一個k-流，促進了四色定理的研究。文[3]提到Tutte的著名猜想：Tutte-3流、Tutte-4流、Tutte-5流猜想，人們圍繞這些問題展開了很多研究，至今上述猜想還未被攻破，因此，研究猜想成立的圖類很有必要。因而，對于圖的擴容變換下獲得的新圖類，研究Tutte猜想很有意義。

參考文獻：

[1]H.Whitney，Congruent graphs and connectivity of graphs. Amer.J.Math，1932.54：p.19

[2]阿勇嘎，斯欽.擴容圖及其譜性質，寶雞文理學院學報，2009. 29（1）：p.4

[3]Douglas B.West，ed.圖論導引，2006，機械工業出版社

[4]徐明曜，ed.有限群導引.1999，科學出版社

[5]Murty U.S.R Bondy J.A.Graph Theory with Applications.1976：The Macmillan Press LTD