一類平面圖的強(qiáng)邊著色

薄朝升，謝德政

（重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 401331）

考慮的圖均為無(wú)向簡(jiǎn)單有限圖.圖G的強(qiáng)邊著色是正常邊著色且任何長(zhǎng)為3的路的邊不著雙色.圖G的強(qiáng)邊色數(shù)是G的所有強(qiáng)邊著色中使用色數(shù)的最小者，記為χ's（G）.

Erd?s和 Nestril［1］提出以下猜想（強(qiáng)邊著色猜想）:對(duì)任意圖G，

對(duì)于 Δ =3 的圖，強(qiáng)邊著色猜想已被證明［2，3］.Horak［4］證明了對(duì)于 Δ =4 的圖，χ's（G）≤23;Cranston［5］利用時(shí)間序列算法證明了對(duì)于Δ=4的圖，χ's（G）≤22.

度為k的點(diǎn)稱為k－點(diǎn);度不小于k的點(diǎn)稱為k+－點(diǎn).設(shè)p是一條長(zhǎng)為k+1的路，且其所有的內(nèi)點(diǎn)（一

定理1 設(shè)圖G是平面圖且滿足g（G）≥14，則

設(shè)圖G是一個(gè)滿足定理?xiàng)l件且含有最少邊的反例（Δ≥3）.則對(duì)于G有以下斷言成立:

斷言1G不含有1－點(diǎn).

圖1 G

斷言2G不含有2（1，1）－點(diǎn).

斷言 3G不含有 3（1，2，2）－點(diǎn).

1{c（uv1），c（uw1）}，要對(duì)uu1著色，需避開(kāi)c（x）∪c（v1）∪c（w1）中的顏色.而|c（x）∪c（v1）∪c（w1）|≤2Δ +1，故至少有3種顏色可用于對(duì)uu1的著色，從而完成了對(duì)G的一個(gè)強(qiáng)邊著色，矛盾.若c（u1x）∈{c（uv1），c（uw1）}，不妨設(shè)c（u1x）=c（uv1）=c.首先對(duì)uv1重新著色，只需避開(kāi)c（v2）∪c（w1）∪{c}中的顏色，顯然，存在顏色c'可用于對(duì)uv1的重新著色，且使得c（u1x）{c'（uv1），c（uw1）}.從而，與上面類似，可完成對(duì)G的一個(gè)強(qiáng)邊著色，矛盾.

綜上，極小反例G不包含斷言1－3的構(gòu)圖.

現(xiàn)在按照法則R1和R2，對(duì)G中的任意點(diǎn)重新賦值，設(shè)新的賦值函數(shù)為ch'，則有以下情況:情況1u是一個(gè)2－點(diǎn).

情況3u是一個(gè)4+－點(diǎn).

［1］ERDOS P，NESETRIL J.Problem.In:G.Halsz and V.T.Sos，Editors，Irregularities of Partitions［M］.New York:Springer，1989

［2］ANDERSEN L A.The strong chromatic index of a cubic graph is at most 10 ［J］.Discrete Math，1992，108（1－3）:231－252

［3］HORAK P，QING H，TROTTER W T.Induced matching in cubic graphs［J］.J Graph Theory，1993，17:151－160

［4］HORAK P.The strong chromatic index of graphs with maximum degree four［J］.Conterp Methods Graphs Theory，1990（8）:399－403

［5］CRANSTON C.Strong edge－coloring of graphs with maximum degree 4 using 22 colors［J］.Discrete Math，2006，306:2772－2778

［6］MONTASSIER M，OCHEM P，RASPAUD A.On the acyclic choosability of graphs［J］.J Graph Theory，2006，51:281－300

［7］BONDY J A，MURTY U S R.Graph Theory［M］.Berlin:Springer，2008

［8］張衛(wèi)標(biāo)，楊清軍.關(guān)于強(qiáng)邊著色猜想的最優(yōu)圖問(wèn)題［J］.重慶工學(xué)院學(xué)報(bào)，2009，26（6）:538－547