论文部分内容阅读
1971年，Berge和Fulkerson提出了著名的Berge-Fulkerson猜想，即每个无割边的3-正则图都有六个完美匹配使得图的每条边恰好在其中的两个完美匹配中.与Berge-Fulkerson猜想等价的就是Berge-Fulkerson着色.设图G是一个无割边的3-正则图，将图G的每条边复制一次成为一对平行边，得到图2G.若图2G是6边可着色的，则称图G有Berge-Fulkerson着色.在研究Berge-Fulkerson着色时，显然，3边可着色的3-正则图一定有Berge-Fulkerson着色，所以主要考虑非3边可着色的3-正则图是否有Berge-Fulkerson着色.通常将无割边的非3边可着色的3-正则图称为snarks.对一些特殊的snarks，包括Flower snarks和Goldberg snarks等，已经被证明有Berge-Fulkerson着色.本文主要研究具有特定八圈结构的任意snarks图的Berge-Fulkerson着色性质，刻画了3-正则图满足Berge-Fulkerson着色的充分条件，并利用这一充分条件证明了包含无限类的很多类snarks有Berge-Fulkerson着色. 本文的结构如下: 第一章是绪论部分，主要介绍研究背景和一些图论的基本概念. 第二章，研究了具有特定八圈结构的3-正则图的Berge-Fulkerson着色，刻画了Berge-Fulkerson着色的充分条件，并利用这一充分条件证明了Flower snarks,Watkinssnarks,Celmins-Swarts snarks和Szekeres-Watkinssnarks这些无限类snarks都有Berge-Fulkerson着色. 第三章，H(a)gglund构造了Blowup(K4，C)和Blowup(Prism，C4)，基于这两类图，Chen构造了无穷图类M0,1，2，…，k-2,k-1，并提出M0，1,2…，k-2，k-1中每一个图都有Berge-Fulkerson着色的猜想，其中k≥1.本章解决了Chen提出的猜想，证明了图类M0,1,2,…,k-2,k-1中的每一个图都有Berge-Fulkerson着色，其中k≥2. 第四章，Marién Abreu等人基于树的平图和Petersen图构造了一类snarks图类，称为Treelike snarks，本章证明了Treelike snarks都有Berge-Fulkerson着色. 第五章，总结全文并提出一些待研究问题.