一類平面圖的強邊著色

薄朝升，謝德政

（重慶大學數學與統計學院，重慶 401331）

考慮的圖均為無向簡單有限圖.圖G的強邊著色是正常邊著色且任何長為3的路的邊不著雙色.圖G的強邊色數是G的所有強邊著色中使用色數的最小者，記為χ's（G）.

Erd?s和 Nestril［1］提出以下猜想（強邊著色猜想）:對任意圖G，

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

度為k的點稱為k－點;度不小于k的點稱為k+－點.設p是一條長為k+1的路，且其所有的內點（一

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

設圖G是一個滿足定理條件且含有最少邊的反例（Δ≥3）.則對于G有以下斷言成立:

斷言1G不含有1－點.

圖1 G

斷言2G不含有2（1，1）－點.

斷言 3G不含有 3（1，2，2）－點.

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

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

現在按照法則R1和R2，對G中的任意點重新賦值，設新的賦值函數為ch'，則有以下情況:情況1u是一個2－點.

情況3u是一個4+－點.

［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］張衛標，楊清軍.關于強邊著色猜想的最優圖問題［J］.重慶工學院學報，2009，26（6）:538－547