强边着色猜想问题的最优图*

2017-06-19张卫标

重庆工商大学学报（自然科学版） 2017年3期

关键词：上界图论商丘

张卫标

(商丘学院计算机工程学院，河南商丘 476000)

强边着色猜想问题的最优图*

张卫标

(商丘学院计算机工程学院，河南商丘 476000)

边着色；强边着色；最优图

强边着色猜想中使得等式成立的图叫做最优图.

此处构造了一族图，并以此证明了, 当最大度为奇数时，如果Erdös和Nešetǐil提出的强边着色猜想成立，则猜想中的上界是最优的.

图1 最大度为4的最优图Fig.1 Optimal graph with maximum degree of 4

引理1 当Δ=3时，存在一个图使得它的强边色数等于强着色猜想的上界，即为最优图.

引理2 当Δ=5时，存在一个图使得它的强边色数等于强边着色猜想的上界，即为最优图.

图2 最大度为3的最优图Fig.2 Optimal graph with maximum degree of 3

图3 最大度为5的最优图Fig.3 Optimal graph with maximum degree of 5

定理1 存在对Δ=2k-1,k=2,…,n的最优图.

下证G′即为Δ=2k-1时的最优图.由定理1知存在Δ=2k-2,k=2,…,n的最优图，这就说明G′中从内到外k-1层5圈及其关联边满足任意两边都在长为3的路上，现只需要说明与顶点vk1,vk2相关联的边与G′中其他边都在长为3的路上，由对称性，不妨考虑两类边vk1vi2(i=1,2,…,k)和vk1vj5(j=1,2,…,k-1).

[1] BONDY J A,MURTY U S R .图论及其应用[M].北京:科学出版社,1999

BONDY J A,MURTY U S R .Graphs and Application[M].Beijing:Science Press,1999

[2] 徐俊明.图论及其应用[M].合肥：中国科学技术出版社，2004

XU J M.Graphs and Application[M].Hefei:Chinese Science and Technology Press,2004

[3] FOUQUET J L,JOLIVET J L.Strong Edge Coloring of Graphs and Applications to Multi-k-Gons[J].Ara Combin,1983(16A):141-150

[4] FOUQUET J L,JOLIVET J L.Strong Edge Coloring of Cubic Planar Graphs:Progress in Graph Theory[M].Toronto:Academic press,1984

[5] CRANSTON D W.Strong Edge Coloring of graphs with Maximum Degree 4 Using 22colors[J].Discrete Math,2006,306:272-278

[6] 柳顺义，陈祥恩.最大度等于5的图的强边色数[J].西北师范大学学报(自然科学版)，2007，43(2):16-19

LIU S Y,CHEN X E.Strong Edge Coloring of Grapha with Maximum Degree 5[J].Journal of Northwest Normal University (Natutal Science Edition),2007,43(2):16-19

[7] 张卫标，杨清军.关于强边着色猜想的最优图问题[J].重庆工商大学学报(自然科学版)，2009,26(6)：538-539

ZHANG W B,YANG Q J.The Optimum Graphs of Strong Edge Coloring Conjecture[J].Journal of Chongqing Technology and Business University (Natural Science Edition),2009,26(6):538-539

责任编辑：李翠薇

The Optimum Graph of Strong Edge Coloring Conjecture

ZHANG Wei-biao

(School of Computer Science and Technology, Shangqiu University, Henan Shangqiu 476000, China)