数学研究
數學研究
수학연구
JOURNAL OF MATHEMATICAL STUDY
2011年
1期
76-85
,共10页
平面图%线性染色%围长%最大度
平麵圖%線性染色%圍長%最大度
평면도%선성염색%위장%최대도
如果图G的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图G的线性染色.图G的线性色数用lc(G)表示,是指G的所有线性染色中所用的最少颜色的个数本文证明了对于每一个最大度为△(G)且围长至少为5的平面图G有lc(G)≤[△(G)/2]+5,并且当△(G)∈{7,8,…,14}时,lc(G)≤[△(G)/2]+4.
如果圖G的一箇正常染色滿足染任意兩種顏色的頂點集閤導齣的子圖是一些點不交的路的併,則稱這箇正常染色為圖G的線性染色.圖G的線性色數用lc(G)錶示,是指G的所有線性染色中所用的最少顏色的箇數本文證明瞭對于每一箇最大度為△(G)且圍長至少為5的平麵圖G有lc(G)≤[△(G)/2]+5,併且噹△(G)∈{7,8,…,14}時,lc(G)≤[△(G)/2]+4.
여과도G적일개정상염색만족염임의량충안색적정점집합도출적자도시일사점불교적로적병,칙칭저개정상염색위도G적선성염색.도G적선성색수용lc(G)표시,시지G적소유선성염색중소용적최소안색적개수본문증명료대우매일개최대도위△(G)차위장지소위5적평면도G유lc(G)≤[△(G)/2]+5,병차당△(G)∈{7,8,…,14}시,lc(G)≤[△(G)/2]+4.