董晓媛

(南通师范高等专科学校数理系，江苏南通 226007)

图G的一个正常k-边染色是用k种颜色对图G的边集进行染色，使得任意相邻的边染不同的颜色.设π是图G的一个正常k-边染色，如果染色π使得图G中有公共边的任意两条边的染色也不相同，则称π是图G的一个k-强边染色.强边染色在无线电通讯网络的无冲突信道分配问题上具有重要的理论和实际意义.

Snark图是源自3-边着色猜想而构造的图，若图是二边连通的3正则图且不可3-边着色，同时围长至少为5，也无非平凡3-边割集，则称为snark.Petersen图是最小的snark.本文对Flower snark图的强边染色进行了研究.下面给出Flower snark图的定义.

定义1Gn是一个简单的非平凡的连通的三正则图，点集V(G)={ai,bi,ci,di:0≤i≤n-1}，边集E(G)={aiai+1,bibi+1,cici+1,diai,dibi,dici:0≤i≤n-1}，点的标号对n取模，Hn可以由Gn通过用边bn-1c0、cn-1b0替换bn-1b0、cn-1c0得到.如果n为奇数且n≥5，Hn被称为Flower snark图，其他的图被称为Flower snark图的相关图.

把这些图统一用Fn来表示，如图1所示.

由定义1，给出F5的一个画法，如图2所示.

a与a相连，b与b相连，c与c相连图1 Fn的一个画法

图2 Flower snark图F5的一个画法

图图示

当n≥5时，为了研究Fn的强边色数，将n分成n=3m+5、n=3m+6、n=3m+7(m为非负整数)三类.

证明 首先给出F5的一个强边染色，如图4所示.

图4 F5的一个强边染色

图的一个强边染色

证明 首先给出F6的一个强边染色，如图6所示.

图6 F6的一个强边染色

图的另一个强边染色

证明 首先给出F7的一个强边染色，如图8所示.

图8 F7的一个强边染色

由引理2、引理3和引理4得到如下结论.

图9 H图示

证明 假设图H可以用5色强边染色.如图9所示，边e1,e2,e3,e4,e5的距离都小于等于3，不能染同一种颜色，这5种颜色不妨记作a,b,c,d,e，令f(e1)=a,f(e2)=b,f(e3)=c，则e4,e5只能染d,e.不妨设f(e4)=d，则f(e5)=e，则e6只能染d,e中的一个.

情形一：若f(e6)=d，则f(e7)≠a,d，则e7只能染b,c,e中的一个.

(1)若f(e7)=b，则f(e8)≠a,b,d,e，则e8只能染c.此时e9不能用a,b,c,d,e五种颜色染色.产生矛盾.

(2)若f(e7)=c，则f(e8)≠a,c,d,e，则e8只能染b.此时e9不能用b,c,d,e染色，所以f(e9)=a，此时e10不能用a,b,c,d,e五种颜色染色.产生矛盾.

(3)若f(e7)=e，则f(e8)≠a,d,e，则e8只能染b,c.

①若f(e8)=b，则f(e9)≠b,d,e，所以f(e9)=a,c.

(ⅰ)若f(e9)=a，则f(e10)≠a,b,c,d,e，此时e10不能用a,b,c,d,e五种颜色染色.产生矛盾.

(ⅱ)若f(e9)=c，则f(e10)≠a,b,d,e，此时f(e10)=a，此时e11只能染d或者e.

②若f(e8)=c，则f(e9)≠b,c,d,e，所以f(e9)=a.则f(e10)≠a,c,d,e，此时f(e10)=b，此时e11只能染d或者e.

情形二：若f(e6)=e，则f(e7)≠a,e，则e7只能染b,c,d中的一个.

(1)若f(e7)=b，则f(e8)≠a,b,e，则e8只能染c,d.

①若f(e8)=c，则f(e9)≠b,c,e，所以f(e9)=a,d.

(ⅰ)若f(e9)=a，则f(e10)≠a,b,c,d,e，此时e10不能用a,b,c,d,e五种颜色染色.产生矛盾.

(ⅱ)若f(e9)=d，则f(e10)≠b,c,d,e，此时f(e10)=a，此时e11只能染e.

②若f(e8)=d，则f(e9)≠b,d,e，所以f(e9)=a,c.

(ⅰ)若f(e9)=a，则f(e10)≠a,b,d,e，此时f(e10)=c，此时e11只能染e.

(ⅱ)若f(e9)=c，则f(e10)≠b,c,d,e，此时f(e10)=a，此时e11只能染e.

(2)若f(e7)=c，则f(e8)≠a,c,e，则e8只能染b,d.

①若f(e8)=b，则f(e9)≠a,b,c,e，所以f(e9)=d.此时f(e10)≠b,c,d,e，此时f(e10)=a，此时e11只能染e.

②若f(e8)=d，则f(e9)≠b,c,d,e，所以f(e9)=a.此时f(e10)≠a,c,d,e，则f(e10)=b，此时e11只能染e.

(3)若f(e7)=d，则f(e8)≠a,d,e，则e8只能染b,c.

①若f(e8)=b，则f(e9)≠b,d,e，所以f(e9)=a,c.

(ⅰ)若f(e9)=a，则f(e10)≠a,b,c,d,e，此时e10不能用a,b,c,d,e五种颜色染色.产生矛盾.

(ⅱ)若f(e9)=c，则f(e10)≠b,c,d,e，此时f(e10)=a，此时e11只能染d或者e.

②若f(e8)=c，则f(e9)≠b,c,d,e，所以f(e9)=a.此时e10不能用a,b,c,d,e五种颜色染色.产生矛盾.

我们发现，在讨论了图H中两个块后，e11只能染d或者e.把两个块推广到6个块，会发现在e11所在的长为3的路上只能染d或者e，与定义矛盾.

由定理1和定理2，得到定理3.