新疆大学学报(自然科学版)
新疆大學學報(自然科學版)
신강대학학보(자연과학판)
JOURNAL OF XINJIANG UNIVERSITY
2003年
3期
233-235
,共3页
点着色%边着色%圈覆盖
點著色%邊著色%圈覆蓋
점착색%변착색%권복개
colorable%edge colorable%cycle cover
设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(θ)是二或三点着色.这个结论给出了一个判定无割边三正则图是三边着色的方法.
設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(θ)是二或三點著色.這箇結論給齣瞭一箇判定無割邊三正則圖是三邊著色的方法.
설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 θ = {C1,C2,… ,CK} be a cycle cover of G. Define a new graph G(θ) = (V,E), where V = {C1 ,C2,... ,Ck} ,(Ci ,Cj) ∈ Eif and only if E(Ci) ∩ E(Cj) ≠φ(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.
