图的相邻强边着色数(英文)  

Adjacent Strong Edge Coloring Number of Graphs

作　　者：杨爱峰[1] 原晋江[1] 

机构地区：[1]郑州大学数学系,郑州450052

出　　处：《郑州大学学报（理学版）》2004年第2期7-9,15,共4页Journal of Zhengzhou University:Natural Science Edition

基　　金：霍英东教育基金资助项目;国家自然科学基金资助项目,编号 10371112.

摘　　要：如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图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.

关 键 词：相邻强边 着色数 顶点集 正则图 完美匹配 

分 类 号：O157.5[理学—数学]