Goldberg snark圖的強邊染色

董曉媛，馬登舉

(1.南通師范高等專科學校數理系，江蘇 南通 226007；2.南通大學理學院，江蘇 南通 226000)

snark圖是源自3-邊著色猜想而構造的圖.若圖是2邊連通的3正則圖且不可3-邊著色，同時圍長至少為5，也無非平凡3-邊割集，則稱為snark圖.

本文對Goldberg snark圖的強邊染色進行了研究.

由定義可給出B3的一個畫法，如圖1所示.

圖1 B3的一個畫法

圖2 Bk的子圖

為了研究Bk的強邊色數，將Bk通過k≡0(mod 3)，k≡1(mod 3)，k≡2(mod 3)，分成三類.

圖的一個強邊染色

圖4 k≡1(mod 3)時B3的一個強邊染色

圖豎線前面首尾相連就是B4)的一個強邊染色

圖6 k≡2(mod 3)時B3的一個強邊染色

圖豎線前面首尾相連就是B5)

由以上3個引理可知：

下面研究Goldberg snark圖的強邊色數的下界.

圖8 Bk的一個子圖H

由定理1與定理2可得如下結論：