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

摘要：

著名图论专家Erd(o)s和Ne(s)et(r)il对图的强边着色数上界提出了一个猜想:当△为偶数时,x's(G)≤5/4△2;当△为奇数时,x's(G)≤1/4(5△2-2△+1),他们给出了当△=4的时的最优图.此处构造了一族图,并以此证明了当△为偶数时,如果Erd(o)s和Ne(s)et(r)il提出的强边着色猜想成立,则猜想中的上界是最优的.

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

所属期刊栏目：26

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2010-03-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：538-539,547