论文标题
不能覆盖四个完美匹配的立方图
Cubic graphs that cannot be covered with four perfect matchings
论文作者
论文摘要
Berge的一个猜想表明，每个无用的立方图都可以覆盖其边缘最多五个完美的匹配。由于仅当相关图形为$ 3 $ - edge色时，只有三个完美的匹配就足够了，因此其余的立方图分为两个类：可以用四个完美匹配覆盖的图表，以及那些至少需要五个。需要超过四个完美匹配才能覆盖其边缘的立方体图特别有趣，因为潜在的反示例对几个深刻而长期的猜想，包括著名的循环双重掩盖猜想。但是，到目前为止，他们很难找到。 在本文中，我们构建了一个理论，该理论将四个完美匹配的覆盖物描述为流动值和流出模式的流动，形成了六行的配置，该配置由三维投影空间的四个点覆盖，$ \ mathbb {p} _3（\ mathbb {f} _2 _2 _2）$。该理论为研究不承认这种封面的图形提供了强大的工具，并为其构建提供了多种方法。作为一个说明性的例子，我们生产了一个丰富的Snark家族（非平凡的立方图，没有$ 3 $ - 边彩色），无法覆盖四个完美的匹配。该家庭包含所有以前已知的图形。
A conjecture of Berge suggests that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. Since three perfect matchings suffice only when the graph in question is $3$-edge-colourable, the rest of cubic graphs falls into two classes: those that can be covered with four perfect matchings, and those that need at least five. Cubic graphs that require more than four perfect matchings to cover their edges are particularly interesting as potential counterexamples to several profound and long-standing conjectures including the celebrated cycle double cover conjecture. However, so far they have been extremely difficult to find. In this paper we build a theory that describes coverings with four perfect match\-ings as flows whose flow values and outflow patterns form a configuration of six lines spanned by four points of the 3-dimensional projective space $\mathbb{P}_3(\mathbb{F}_2)$ in general position. This theory provides powerful tools for investigation of graphs that do not admit such a cover and offers a great variety of methods for their construction. As an illustrative example we produce a rich family of snarks (nontrivial cubic graphs with no $3$-edge-colouring) that cannot be covered with four perfect matchings. The family contains all previously known graphs with this property.
