三正则图的完美匹配覆盖

Subgraph coverings is one of the most basic research topics in graph theory. In this project, we study the problem on perfect matching coverings of cubic graphs. About this problem, there are two famous conjectures： Berge Conjecture and Fulkerson Conjecture. Berge Conjecture states that every cubic bridgeless graph has 5 perfect matchings such that each edge is contained in at least one of them. Fulkerson Conjecture states that every cubic bridgeless graph has 6 perfect matchings such that each edge is exactly contained in two of them. These two conjectures are equivalent in fact. So far, the two conjectures has only been verified in few cubic graphs. In this project, we will promote the research on Berge Conjecture and Fulkerson Conjecture by verifying Berge Conjecture or Fulkerson Conjecture on some classes of cubic graphs and searching for an upper bound of the minimum number of perfect matchings which can cover all the edgs of a cubic bridgeless graph.

子图覆盖是图论学科最具基础性的研究课题之一。本项目研究的是三正则图的完美匹配覆盖问题。关于这个问题，有两个著名的猜想：Berge猜想和Fulkerson猜想。Berge猜想认为：每一个不含割边的三正则图都有5个完美匹配，使得每一条边都至少包含在其中的一个完美匹配中。Fulkerson猜想认为：每一个不含割边的三正则图都有6个完美匹配，使得每一条边都恰好包含在其中的两个完美匹配中。这两猜想事实上是等价的。目前，这两猜想仅在非常有限的三正则图上得到了论证。本项目，将从论证Berge猜想或Fulkerson猜想在具体的三正则图类上的成立性和探索最少的能够覆盖三正则图的边集的完美匹配数目的上界这两方面，推进Berge猜想和Fulkerson猜想的研究。

子图覆盖是图论学科最具基础性的研究课题之一。本项目研究的是三正则图的完美匹配覆盖问题。关于这个问题，有两个著名的猜想：Berge猜想和Fulkerson猜想。Berge猜想认为：每一个不含割边的三正则图都有5个完美匹配，使得每一条边都至少包含在其中的一个完美匹配中。Fulkerson猜想认为：每一个不含割边的三正则图都有6个完美匹配，使得每一条边都恰好包含在其中的两个完美匹配中。这两个猜想被证实是等价的。. 关于这两个猜想，除了三边可染的三正则图外，目前知道的满足这两猜想图类非常少。对于 Berge 猜想，还有一个弱一些的公开而仍未解决的问题: 是否存在一个常数 c，使得每一个三正则无割边图都有至多 c 个能够覆盖该图所有边的完美匹配？Berge猜想认为存在这样的常数5。. 本项目在一些特殊图类上探讨了Berge猜想和上面这个比Berge猜想弱的公开问题，取得了两个结果。第一个结果是，在奇度为2的三正则图上回答了比Berge猜想弱一些的公开问题。我们证明了奇度为2的三正则图的边集是可以被常数个完美匹配覆盖的，并且我们得到的这个常数是11。第二个结果是，证明了含有两个至多相交于一条边的完美匹配的三正则无割边的图是满足Berge猜想的。我们的这两个结果是首次在一个完整的非平凡图类上论证Berge猜想或回答那个比Berge猜想弱的公开问题。