Goldberg snark圖的強(qiáng)邊染色

董曉媛，馬登舉

(1.南通師范高等?？茖W(xué)校數(shù)理系，江蘇 南通 226007；2.南通大學(xué)理學(xué)院，江蘇 南通 226000)

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

本文對(duì)Goldberg snark圖的強(qiáng)邊染色進(jìn)行了研究.

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

圖1 B3的一個(gè)畫法

圖2 Bk的子圖

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

圖的一個(gè)強(qiáng)邊染色

圖4 k≡1(mod 3)時(shí)B3的一個(gè)強(qiáng)邊染色

圖豎線前面首尾相連就是B4)的一個(gè)強(qiáng)邊染色

圖6 k≡2(mod 3)時(shí)B3的一個(gè)強(qiáng)邊染色

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

由以上3個(gè)引理可知：

下面研究Goldberg snark圖的強(qiáng)邊色數(shù)的下界.

圖8 Bk的一個(gè)子圖H

由定理1與定理2可得如下結(jié)論：