Adjacent Strong Edge Chromatic Number of Series-Parallel Graphs |
Received:January 13, 2003 |
Key Words:
series-parallel graph adjacent strong edge coloring adjacent strong edge chromatic number.
|
Fund Project:National Natural Science Foundation of China (60103021, 60274026) |
Author Name | Affiliation | WANG Shu-dong | College of Info. Sci. Eng., Shandong University of Sci. Technology, Tai'an 271019, China Dept. of Control Sci. Eng., Huazhong University of Sci. Technology, Wuhan 430074, China | PANG Shan-chen | College of Info. Sci. Eng., Shandong University of Sci. Technology, Tai'an 271019, China | XU Jin | Dept. of Control Sci. Eng., Huazhong University of Sci. Technology, Wuhan 430074, China |
|
Hits: 2524 |
Download times: 1305 |
Abstract: |
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. |
Citation: |
DOI:10.3770/j.issn:1000-341X.2005.02.008 |
View Full Text View/Add Comment |
|
|
|