亚Hamilton图的四线染色和Fulkerson染色

摘要

Fulkerson猜想指的是对于一个无桥三正则图，一定存在六个完美匹配，使得每条边刚好落在其中2个匹配之中。这个问题困扰了人们很多年。我们知道，对于一个可以三边染色的三正则图，结果是显而易见的；但是对与无法三边染色，即只可四边染色的三正则图（我们通常称之为Snark），结果就不那么容易给出了。所以研究Snark成为了证明Fulkerson猜想的重要方法。但是对于Snark的结构，我们很难给出一个非常好的定性的描述，我们只能一类一类研究。在1994年，范更华和Raspaud提出了一个弱化的猜想，即任意一个无桥三正则图G，必定含有三个完美匹配M1，M2，M3满足M1∩M2∩M3=(Φ)．在2005年，Edita Macajova和Martin Skoviera义证明了Fan-Raspaud猜想与四线染色猜想的等价性。本文就是研究一类snark-亚Hamilton图是否满足Fulkerson猜想和Fan-raspaud猜想，并得到了下面三个结论：
　　 (1)证明了亚Hamilton图是满足四线染色猜想的，从而它是满足Fan-raspaud猜想的；
　　 (2)证明了若存在Fulkerson猜想的最小反例图G，则G的围长至少为5；
　　 (3)给出了一类满足Fulkerson猜想的亚Hamilton图。