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

• 作 者: 张卫标 杨清军
• 机 构: 重庆大学数理学院
• 出 处: 重庆工商大学学报：自然科学版
• 发表日期: 2009年6期
• 关键词: 边着色 强边着色 最优图 edge coloring strong edge-coloring optimum graph

著名图论专家Erdos和Nesetril对图的强边着色数上界提出了一个猜想：当△为偶数时，Xs＇（G）≤5/4△^1；当△为奇数时Xs＇（G）≤1/4（5△^2-2△＋1），他们给出了当△=4的时的最优图．此处构造了一族图，并以此证明了当A为偶数时，如果Erdos和Nesettil提出的强边着色猜想成立，则猜想中的上界是最优的．