平面圖的無圈邊染色

王藝橋，舒巧君

（1.北京中醫(yī)藥大學(xué) 管理學(xué)院，北京 100029；2.杭州電子科技大學(xué) 理學(xué)院，浙江 杭州 310018）

0 引言

本文考慮有限簡(jiǎn)單圖.給定一個(gè)圖G，用V（G）和E（G）分別表示它的頂點(diǎn)集和邊集.令Ck＝u1u2…uku1是G中長為k的圈.若兩個(gè)圈至少有一條公共邊，就稱這兩個(gè)圈為相鄰的.設(shè)Δ和δ分別表示一個(gè)圖G的最大度和最小度.

圖G的正常邊k染色是指映射c：E（G）→｛1，2，…，k｝，使得相鄰的邊染不同的顏色.G 的邊色數(shù)χ′（G）是指使得G是邊k可染的最小整數(shù)k.無圈邊k染色是指G的一個(gè)正常的邊k染色，使得不產(chǎn)生雙色圈.無圈邊色數(shù)a′（G）是指使得G是無圈邊k染色的最小整數(shù)k.由著名的Vizing's定理知，Δ≤χ′（G）≤Δ＋1.因此，顯然有a′（G）≥χ′（G）≥Δ.Fiamˇcik［1］，Alon等［2］先 后 分 別 提 出 了 著 名 的 無 圈邊色數(shù)猜想.

猜想1 對(duì)任何圖G，a′（G）≤Δ＋2.

1991年，Alon等［3］應(yīng)用概率方法證明了對(duì)任何圖G，有a′（G）≤64Δ.當(dāng)前最好的上界a′（G）≤4Δ－4，由Esperet等［4］得到.一些特殊圖的無圈邊染色已被廣泛研究，如最大度為3的圖［5］，為4的圖［6－7］.對(duì) 于 平 面 圖 G，Basavaraju 等［8］證 明 了a′（G）≤Δ＋12.Wang等［9］將12降到7，且證明了當(dāng)G符合以下幾個(gè)條件之一時(shí)，猜想1成立：i）不含3圈［10］；ii）不含4圈［11］；iii）不含5圈［12］；iv）不含3圈和4圈相鄰［13］.相關(guān)結(jié)果參見［14］.

本文旨在研究不含3圈和5圈相鄰的平面圖的無圈邊色數(shù).將證明此類圖也是滿足猜想1的，這在一定程度上改進(jìn)了文獻(xiàn)［11－12］中的結(jié)果和擴(kuò)充了［13］中的結(jié)果.

1 結(jié)構(gòu)分析

給定一個(gè)圖G，令dG（v）（或d（v））表示頂點(diǎn)v在G中的度.度為k（至少為k，至多為k）的頂點(diǎn)稱為k點(diǎn)（k＋點(diǎn)，k－點(diǎn)）.對(duì)于平面圖H，用F（H）表示其面集合，并用dH（f）（或d（f））表示面f∈F（H）的度.類似地，可定義k面，k＋面以及k－面.對(duì)于f∈F（H），用b（f）表示面f的邊界，若一個(gè)面f沿著某 個(gè) 方 向 的 點(diǎn) 依 次 為 u1，u2，…，un，則 記 為f＝［u1u2…un］.

引理1 設(shè)G為Δ≥5的2連通平面圖，且不含相鄰的3圈和5圈，則G含以下子構(gòu)型A1）～A6）之一（見圖1）：