无割边三正则图三边着色的一个充分必要条件(英文)

Sufficient and Necessary Condition for the 3-edge Colorable Cubic Graph

设G是无割边三正则图,θ={C1,C2,…,Ck}是G一个圈覆盖,定义一新图G(θ)=(V,E),这里V={C1,C2,…,Ck},(Ci,Cj)∈E当且仅当E(Ci)∩E(Cj)≠ (1≤i≠j≤k).那么G是三边着色的充分必要条件是G有一个圈的一或二次覆盖θ并且G(θ)是二或三点着色.这个结论给出了一个判定无割边三正则图是三边着色的方法.

Let \$G\$ be a bridgeless cubic graph and \$θ=｛C\-1,C\-2,…,C\-K｝\$ be a cycle cover of G.Define a new graph \$G(θ)=(V,E),\$ where \$V=｛C\-1,C\-2,…,C\-k｝,(C\-i,C\-j)∈E\$ if and only if \$E(C\-i)∩E(C\-j)≠(1≤i≠j≤k).\$ Then \$G\$ is 3edge colorable if and only if \$G\$ has a cycle (1,2)cover \$θ\$ such that \$G(θ)\$ is 2 or 3colorable,which gives a way to verify a bridgeless cubic graph to be 3edge colorable.