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