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可得如下结论：