论文标题
Berge的猜想，用于具有小色缺陷的立方图
Berge's conjecture for cubic graphs with small colouring defect
论文作者
论文摘要
长期以来，伯格（Berge）的一个猜想表明，每个无用的立方图都可以表示为最多五个完美匹配的结合。这种猜想的态度在$ 3 $ - 边色的立方图上均以$ 3 $ - 不可售价为$ 3 $ - edge色的图形开放。本文的目的是验证Berge猜想在某种意义上接近$ 3 $ - edge-colourable图的有效性。我们通过查看着色缺陷来衡量接近度，该缺陷被定义为任何三个完美匹配的收藏集所揭示的最小边数。虽然$ 3 $ - edge色的图具有缺陷$ 0 $，但每个无用的立方图，没有$ 3 $ edge-edge-the-edge-thecoring the，至少有$ 3 $。 2015年，Steffen证明了Berge的猜想具有周期性$ 4 $ - 边缘连接的立方图，并具有着色缺陷$ 3 $或$ 4 $。我们的目的是通过两种方式改善Steffen的结果。我们表明，所有具有缺陷的无用的立方图$ 3 $满足Berge的猜想，无论其周期性连通性如何。如果此外，该图是周期性的$ 4 $ - 边缘连接的，则四个完美的匹配就足够了，除非该图是Petersen图。结果是最好的，因为存在一个无限的立方图系列，并具有循环连接性$ 3 $，其缺陷$ 3 $，但不能覆盖四个完美的匹配。
A long-standing conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. This conjecture trivially holds for $3$-edge-colourable cubic graphs, but remains widely open for graphs that are not $3$-edge-colourable. The aim of this paper is to verify the validity of Berge's conjecture for cubic graphs that are in a certain sense close to $3$-edge-colourable graphs. We measure the closeness by looking at the colouring defect, which is defined as the minimum number of edges left uncovered by any collection of three perfect matchings. While $3$-edge-colourable graphs have defect $0$, every bridgeless cubic graph with no $3$-edge-colouring has defect at least $3$. In 2015, Steffen proved that the Berge conjecture holds for cyclically $4$-edge-connected cubic graphs with colouring defect $3$ or $4$. Our aim is to improve Steffen's result in two ways. We show that all bridgeless cubic graphs with defect $3$ satisfy Berge's conjecture irrespectively of their cyclic connectivity. If, additionally, the graph in question is cyclically $4$-edge-connected, then four perfect matchings suffice, unless the graph is the Petersen graph. The result is best possible as there exists an infinite family of cubic graphs with cyclic connectivity $3$ which have defect $3$ but cannot be covered with four perfect matchings.
