图的相邻强边着色数

摘要：

如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'aa(G)≤3△(G)+1.

关键词：相邻强边、着色、着色数

所属期刊栏目：36

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

资助基金：教育部霍英东教育基金;国家自然科学基金10371112

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

页数：共4页

页码：7-9,15