淮阴师范学院学报（自然科学版）
淮陰師範學院學報（自然科學版）
회음사범학원학보（자연과학판）
JOURNAL OF HUAIYIN TEACHERS COLLEGE (NATURAL SCIENCE EDITION)
2009年
2期
112-114
,共3页
外部平面图%列表染色%平方图
外部平麵圖%列錶染色%平方圖
외부평면도%렬표염색%평방도
图G的平方图,记作G2,是一个以原图的顶点集作为顶点集,若原图中两点的距离不大于2则连以边所成的图.图G的列表染色数,记作χl(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在G顶点的一个正常染色.设G是一个最大度为Δ(G)的2-连通外部平面图,则χl(G2)≤Δ(G)+2.
圖G的平方圖,記作G2,是一箇以原圖的頂點集作為頂點集,若原圖中兩點的距離不大于2則連以邊所成的圖.圖G的列錶染色數,記作χl(G),定義為最小的自然數k,使得滿足:對任一頂點給定k種顏色的列錶,且染色時每箇頂點的顏色隻能從自身的顏色列錶中選擇時,總存在G頂點的一箇正常染色.設G是一箇最大度為Δ(G)的2-連通外部平麵圖,則χl(G2)≤Δ(G)+2.
도G적평방도,기작G2,시일개이원도적정점집작위정점집,약원도중량점적거리불대우2칙련이변소성적도.도G적렬표염색수,기작χl(G),정의위최소적자연수k,사득만족:대임일정점급정k충안색적렬표,차염색시매개정점적안색지능종자신적안색렬표중선택시,총존재G정점적일개정상염색.설G시일개최대도위Δ(G)적2-련통외부평면도,칙χl(G2)≤Δ(G)+2.
