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

The Optimum Graph of Strong Edge Coloring Conjecture

著名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的.

The famous graph theory expert Erdos and Nesetiil 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 a graph 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 when Δ is odd.