三正则图的正常6-边染色下边的规范性

Normal Edges of 6-Edge Coloring of Cubic Graphs

摘要: 本文围绕规范6-边着色猜想进行研究，该猜想断言任意无桥三正则图存在规范6-边染色。三正则图$G$ 的奇度$\omega \left(G\right)$ 是指$G-M$ 中奇圈个数的最小值，其中$M$ 遍历$G$ 的任意完美匹配。奇度的大小能够衡量图离3-边可染的远近。本文证明了任意无桥三正则图$G$ 存在正常6-边染色，使得非规范边数至多为$4\omega \left(G\right)$ 。

Abstract: The paper studies the normal 6-edge coloring conjecture, which asserts that every bridgeless cubic graph has a normal 6-edge coloring. The oddness of a cubic graph $G$ , denoted by $\omega \left(G\right)$ , is defined as the minimum number of odd cycles $G-M$ contains, where $M$ goes over any perfect matching of $G$ . The oddness $\omega \left(G\right)$ serves as a measure of how close the graph $G$ is to being 3-edge colorable. The paper proves that every bridgeless cubic graph has a proper 6-edge coloring such that the number of non-normal edges is at most $4\omega \left(G\right)$ .