王淑栋,庞善臣,许进.系列平行图的邻强边色数(英文)[J].数学研究及应用,2005,25(2):267~278 |
系列平行图的邻强边色数(英文) |
Adjacent Strong Edge Chromatic Number of Series-Parallel Graphs |
投稿时间:2003-01-13 |
DOI:10.3770/j.issn:1000-341X.2005.02.008 |
中文关键词: 系列平行图 邻强边染色 邻强边色数 |
英文关键词:series-parallel graph adjacent strong edge coloring adjacent strong edge chromatic number. |
基金项目: |
作者 | 单位 | 王淑栋 | 山东科技大学信息科学与工程学院,山东,泰安,271019 华中科技大学控制科学与工程系,湖北,武汉,430074 | 庞善臣 | 山东科技大学信息科学与工程学院,山东,泰安,271019 | 许进 | 华中科技大学控制科学与工程系,湖北,武汉,430074 |
|
摘要点击次数: 2525 |
全文下载次数: 1305 |
中文摘要: |
本文研究了系列平行图的邻强边染色.从图的结构性质出发,利用双重归纳和换色的方法证明了对于△(G)=3,4的系列平行图满足邻强边染色猜想;对于△(G)≥5的系列平行图G, 有△(G)≤x′as(G)≤△(G)+1,且x′as(G)=△(G)+1当且仅当存在两个最大度点相邻,其中△(G)和x′as(G)分别表示图G的最大度和邻强边色数. |
英文摘要: |
In this paper, we will study the adjacent strong edge coloring of series-parallel graphs, and prove that series-parallel graphs of △(G) = 3 and 4 satisfy the conjecture of adjacent strong edge coloring using the double inductions and the method of exchanging colors from the aspect of configuration property. For series-parallel graphs of △(G) ≥ 5, △(G) ≤ x′as(G) ≤△(G) + 1. Moreover, x′as(G) = △(G) + 1 if and only if it has two adjacent vertices of maximum degree, where △(G) and x′as(G) denote the maximum degree and the adjacent strong edge chromatic number of graph G respectively. |
查看全文 查看/发表评论 下载PDF阅读器 |
|
|
|