Petersen染色猜想的可能最小反例

The Possible Minimum Counterexample of Petersen Colouring Conjecture

摘要: Petersen染色猜想是图论在完美匹配方向上的一个仍未被证明的重要猜想，其表述为任意一个无桥三正则图都有Petersen染色。1985年，Jaeger证明了Petersen染色猜想等价于任意一个无桥三正则图都有normal 5-边染色。若无桥三正则图G有一个正常5-边染色，对于图G中的任一条边，其四条邻边与这条边总共用了3种或5种颜色，则称该正常5-边染色是图G的一种normal 5-边染色，其中与邻边共用了3种颜色的边被称为穷边，与邻边共用了5种颜色的边被称为富边。关于这两个猜想的结论大多是在一些特殊图类上，但对于一些长久存在的猜想，也有部分学者考虑其可能最小反例的性质，本文从Petersen染色猜想的等价猜想的性质出发研究Petersen染色猜想的可能最小反例的性质，证得Petersen染色猜想的可能最小反例必然是循环4-边连通的。

Abstract: Petersen colouring conjecture is an important unresolved conjecture in graph theory in the direction of perfect matchings, which states that every bridgeless cubic graph has a Petersen colouring. In 1985, Jaeger proved that the Petersen colouring conjecture is equivalent to the statement that every bridgeless cubic graph has a normal 5-edge-colouring. If a bridgeless cubic graph G has a normal 5-edge-colouring such that for any edge in graph G, the four adjacent edges together with this edge use either 3 or 5 colours, this normal 5-edge-colouring is called a normal 5-edge-colouring of graph G, where edges sharing 3 colours with adjacent edges are called poor edges and edges sharing 5 colours with adjacent edges are called rich edges. Most conclusions about these two conjectures are on some special classes of graphs, but for some long-standing conjectures, some scholars have also considered the properties of their possible minimum counterexample. This paper studies the properties of possible minimum counterexample of the Petersen colouring conjecture from the perspective of the equivalent conjecture’s properties and proves that a possible minimum counterexample of the Petersen colouring conjecture must be cyclically 4-edge-connected.