Adjacent Strong Edge Chromatic Number of Series-Parallel Graphs  

系列平行图的邻强边色数(英文)

作　　者：王淑栋[1] 庞善臣[1] 许进[2] 

机构地区：[1]山东科技大学信息科学与工程学院,山东泰安271019 [2]华中科技大学控制科学与工程系,湖北武汉430074

出　　处：《Journal of Mathematical Research and Exposition》2005年第2期267-278,共12页数学研究与评论（英文版）

基　　金：National Natural Science Foundation of China (60103021, 60274026)

摘　　要：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.本文研究了系列平行图的邻强边染色.从图的结构性质出发,利用双重归纳和换色的方法证明了对于△(G)=3,4的系列平行图满足邻强边染色猜想;对于△(G)≥5的系列平行图G, 有△(G)≤x'as(G)≤△(G)+1,且x'as(G)=△(G)+1当且仅当存在两个最大度点相邻,其中△(G)和x'as(G)分别表示图G的最大度和邻强边色数.

关 键 词：series-parallel graph adjacent strong edge coloring adjacent strong edge chromatic number. 

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