山东大学学报（理学版）
山東大學學報（理學版）
산동대학학보（이학판）
JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
2014年
4期
44-49
,共6页
染色%无圈%三角形
染色%無圈%三角形
염색%무권%삼각형
coloring%acyclic%triangle
图G的正常边染色称为无圈的，如果图G中不含2-色圈。图G的无圈边色数，用a′（ G）表示，是使图G存在正常无圈边染色所需要的最少颜色数。证明了如果不含三角形的轮胎图G的最大度为Δ（ G），则a′（ G）≤Δ（ G）＋3。
圖G的正常邊染色稱為無圈的，如果圖G中不含2-色圈。圖G的無圈邊色數，用a′（ G）錶示，是使圖G存在正常無圈邊染色所需要的最少顏色數。證明瞭如果不含三角形的輪胎圖G的最大度為Δ（ G），則a′（ G）≤Δ（ G）＋3。
도G적정상변염색칭위무권적，여과도G중불함2-색권。도G적무권변색수，용a′（ G）표시，시사도G존재정상무권변염색소수요적최소안색수。증명료여과불함삼각형적륜태도G적최대도위Δ（ G），칙a′（ G）≤Δ（ G）＋3。
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G.The acyclic edge chromatic number of G, denoted by a′( G) , is the least number of colors in an acyclic edge coloring of G.It is proved that if a triangle-free toroidal graph G has maximum degreeΔ(G), then a′(G)≤Δ(G)+3.
