王涛,刘明菊,李德明.路与圈图的联图的均匀强边染色[J].数学研究及应用,2012,32(1):11~18
路与圈图的联图的均匀强边染色
Equitable Strong Edge Coloring of the Joins of Paths and Cycles
投稿时间:2010-05-30  最后修改时间:2011-01-12
DOI:10.3770/j.issn:2095-2651.2012.01.002
中文关键词:  邻强边染色  均匀边染色  路联图    最大度  边色数.
英文关键词:adjacent strong edge coloring  equitable edge coloring  joins of paths  cycle, maximum degree  chromatic index.
基金项目:中央高校基本科研业务费资助(Grant No.2011B019),国家自然科学基金(Grant Nos.10971144;11101020; 11171026),北京市自然科学基金(Grant No.1102015).
作者单位
王涛 华北科技学院基础部, 河北 三河 065201 
刘明菊 北京航空航天大学数学系, 北京 100083 
李德明 首都师范大学数学系, 北京 100048 
摘要点击次数: 1573
全文下载次数: 1423
中文摘要:
      对于图$G$的一个正常边染色$c$,如果相邻的点所关联的边集的色集不相等,$c$称为邻强边染色.图$G$的邻强边染色所需要的最小值称为图$G$的邻强边色数. 如果每个色类所含的边数最多差一,$c$被称为均匀边染色.其最小值称为图$G$的均匀边色数.本文确定了路与圈图的联图有均匀邻强边染色所需要的颜色数的最小值即均匀邻强边色数.
英文摘要:
      For a proper edge coloring $c$ of a graph $G$, if the sets of colors of adjacent vertices are distinct, the edge coloring $c$ is called an adjacent strong edge coloring of $G$. Let $c_i$ be the number of edges colored by $i$. If $|c_i-c_j|\le 1$ for any two colors $i$ and $j$, then $c$ is an equitable edge coloring of $G$. The coloring $c$ is an equitable adjacent strong edge coloring of $G$ if it is both adjacent strong edge coloring and equitable edge coloring. The least number of colors of such a coloring $c$ is called the equitable adjacent strong chromatic index of $G$. In this paper, we determine the equitable adjacent strong chromatic index of the joins of paths and cycles. Precisely, we show that the equitable adjacent strong chromatic index of the joins of paths and cycles is equal to the maximum degree plus one or two.
查看全文  查看/发表评论  下载PDF阅读器