摘要
如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'as(G)≤3△(G)+1.
A proper edge coloring of a graph is called an adjacent strong edge coloring if no two of its adjacent vertices are incident with edges colored by the same set of colors. The adjacent strong chromatic number of a graph C, denoted by x'as(G),is the least number of colors required for an adjacent strong edge coloring of G. Two upper bounds are obtained for x'as(G):one is that x'as(G) ≤ 16d for any d-regular graph G(d≥ 3).the other is that X'as(G)≤ 3△(G) + 1 for any graph G with two edge-disjoint perfect matchings.
出处
《郑州大学学报（理学版）》
CAS
2004年第2期7-9,15,共4页
Journal of Zhengzhou University:Natural Science Edition
基金
霍英东教育基金资助项目
国家自然科学基金资助项目,编号 10371112.
