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

On the optimum graph of strong edge coloring conjecture

著名图论专家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.