張 衛(wèi) 標(biāo)

(商丘學(xué)院 計算機工程學(xué)院，河南 商丘 476000)

強邊著色猜想問題的最優(yōu)圖*

張 衛(wèi) 標(biāo)

(商丘學(xué)院 計算機工程學(xué)院，河南 商丘 476000)

邊著色；強邊著色；最優(yōu)圖

強邊著色猜想中使得等式成立的圖叫做最優(yōu)圖.

此處構(gòu)造了一族圖，并以此證明了, 當(dāng)最大度為奇數(shù)時，如果Erd?s和Ne?etǐil提出的強邊著色猜想成立，則猜想中的上界是最優(yōu)的.

圖1 最大度為4的最優(yōu)圖Fig.1 Optimal graph with maximum degree of 4

引理1 當(dāng)Δ=3時，存在一個圖使得它的強邊色數(shù)等于強著色猜想的上界，即為最優(yōu)圖.

引理2 當(dāng)Δ=5時，存在一個圖使得它的強邊色數(shù)等于強邊著色猜想的上界，即為最優(yōu)圖.

圖2 最大度為3的最優(yōu)圖Fig.2 Optimal graph with maximum degree of 3

圖3 最大度為5的最優(yōu)圖Fig.3 Optimal graph with maximum degree of 5

定理1 存在對Δ=2k-1,k=2,…,n的最優(yōu)圖.

下證G′即為Δ=2k-1時的最優(yōu)圖.由定理1知存在Δ=2k-2,k=2,…,n的最優(yōu)圖，這就說明G′中從內(nèi)到外k-1層5圈及其關(guān)聯(lián)邊滿足任意兩邊都在長為3的路上，現(xiàn)只需要說明與頂點vk1,vk2相關(guān)聯(lián)的邊與G′中其他邊都在長為3的路上，由對稱性，不妨考慮兩類邊vk1vi2(i=1,2,…,k)和vk1vj5(j=1,2,…,k-1).

[1] BONDY J A,MURTY U S R .圖論及其應(yīng)用[M].北京:科學(xué)出版社,1999

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

[2] 徐俊明.圖論及其應(yīng)用[M].合肥：中國科學(xué)技術(shù)出版社，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的圖的強邊色數(shù)[J].西北師范大學(xué)學(xué)報(自然科學(xué)版)，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] 張衛(wèi)標(biāo)，楊清軍.關(guān)于強邊著色猜想的最優(yōu)圖問題[J].重慶工商大學(xué)學(xué)報(自然科學(xué)版)，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

責(zé)任編輯：李翠薇

The Optimum Graph of Strong Edge Coloring Conjecture

ZHANG Wei-biao

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

edge coloring; strong edge-coloring; the optimal graph

10.16055/j.issn.1672-058X.2017.0003.005

2016-05-19；

2016-07-13. * 基金項目：國家自然科學(xué)基金 (青年基金)項目(11201371).

張衛(wèi)標(biāo)(1980-)，男，講師，從事圖論及其應(yīng)用研究.

O157.5

A

1672-058X(2017)03-0021-03