CAJ | 학술논문

本文研究了系列平行图的邻强边染色.从图的结构性质出发,利用双重归纳和换色的方法证明了对于△(G)=3,4的系列平行图满足邻强边染色猜想;对于△(G)≥5的系列平行图G,有△(G)≤x′as(G)≤△(G)+1,且x′as(G)=△(G)+1当且仅当存在两个最大度点相邻,其中△(G)和x′as(G)分别表示图G的最大度和邻强边色数.
본문연구료계렬평행도적린강변염색.종도적결구성질출발,이용쌍중귀납화환색적방법증명료대우△(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.