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

On the optimum graph of strong edge coloring conjecture

作　　者：张卫标[1] 杨清军[1] 

机构地区：[1]重庆大学数理学院,重庆400030

出　　处：《重庆工商大学学报（自然科学版）》2009年第6期538-539,547,共3页Journal of Chongqing Technology and Business University:Natural Science Edition

摘　　要：著名图论专家Erds和Neetil对图的强边着色数上界提出了一个猜想:当Δ为偶数时,χ′s(G)≤5/4Δ2;当Δ为奇数时,χ′s(G)≤1/4(5Δ2-2Δ+1),他们给出了当Δ=4的时的最优图.此处构造了一族图,并以此证明了当Δ为偶数时,如果Erd s和Neetil提出的强边着色猜想成立,则猜想中的上界是最优的.In 1985, the famous graph theory expert Erdos and Nesetril conjectured that strong edge-coloring number of a graph is bounded above by 5/4△^2 when △ is even and 1/4（5△^2-2△＋1） when △ is odd. They gave agraph of △= 4. In this paper, we construct a series of such graphs, and prove that if the Strong Edge Coloring Conjecture is correct, the boundary number is optimum.

关 键 词：边着色 强边着色 最优图 

分 类 号：O157.5[理学—数学]