3-正则图的核理论及其应用

In the theory on perfect matchings of graphs, Fulkerson Conjecture is a conjecture in the central place. Fulkerson Conjecture states that every bridgeless cubic graph has six perfect matchings such that each edge is contained in precisely two of them. The theory on cores of cubic graphs was introduced recently. It provides a new way to consider some problems. In this project, we will apply the theory on cores to study Fulkerson Conjecture and three related conjectures, including Petersen Coloring Conjecture, Berge Conjecture and Fan-Raspaud Conjecture. So far, these four conjectures were verified for only a few classes of cubic graphs. First, we will consider a question related to the Petersen coloring conjecture, and expect to give a positive answer to this question. Then, for each remaining conjecture, we will search for a more relaxed condition in terms of cores under which this conjecture holds. On one hand, this project applies the theory on cores of cubic graphs to study these four conjectures. On the other hand, this study will enrich the theory on cores itself.

在图的完美匹配理论中，Fulkerson猜想是其中的一个核心猜想。Fulkerson猜想断言：每个无桥的3-正则图都有六个完美匹配，使得每条边包含在其中的恰好两个完美匹配上。3-正则图的核理论是近些年引入的一种新的研究方法。本项目将应用3-正则图的核理论来研究Fulkerson猜想及其相关联的另外三个重要猜想：Petersen着色猜想、Berge猜想和Fan-Raspaud猜想。目前，这四个猜想仅在非常有限的图类上得到了验证。本项目将考虑一个与Petersen着色猜想相关的问题，期望得到该问题的一个肯定的解答。对于其余三个猜想，本项目将通过核给出一些更为宽泛的图类，并论证猜想在这些图类上是成立的。一方面，本项目运用3-正则图的核理论来推动对以上四个猜想的研究；另一方面，在研究过程中，核理论本身也将得到丰富。

本项目考虑图的完美匹配理论中的2个重要猜想：Petersen着色猜想和Berge猜想，其中Petersen着色猜想强于Berge猜想。鉴于平面图存在以下等价关系：四色定理等价于命题“任意的无桥3-正则平面图的边集可剖分为3个完美匹配”，本项目还考虑四色定理的推广问题和平面图的3-色可染性。. 首先，关于Petersen着色猜想，我们证明了：每一个无桥3-正则图G存在正常的5-边着色，使得至多μ_3(G)条边为非规范边（因此，至少27/35比例的边为规范边）。该结论较好地解答了Petersen着色猜想的弱化问题。该结论不仅较大地改进了已知结果，也引起其他学者的关注和对更一般的k-边着色情形下类似问题的探讨。. 其次，关于Berge猜想，我们证明了：对任意的r-图，用k个完美匹配组成的边覆盖在整个边集中的最大占比m(r,k)的一个下界。特别地，若取k=2r-1，该结论为广义Berge猜想的弱化问题提供一个初步的解答，即m(r,k)至少为86.5%。. 此外，关于四色定理的推广，我们提出更为一般的广义符号图染色（即S-k-染色）的概念，并证明了四色定理在S-4-染色的框架下不能作任何加强。. 最后，关于平面图的3-色可染性，我们证明了：任意不含有4-圈和6-圈的简单平面图都是(1,0,0)-可染的。该结论改进了数个已知结果，是Steinberg猜想的类似问题关于(1,0,0)-可染性的第一个结论。