CAJ | 학술논문

图G的平方图,记作G2,是一个以原图的顶点集为顶点集,若原图中两点的距离不大于2则连以边所成的图.本文确定了圈的平方图的色数.对于外部平面图,得到以下结论:设G是一个最大度为Δ(G)的简单连通外部平面图,G≠C5.则χ(G2)≤Δ(G)+2.
도G적평방도,기작G2,시일개이원도적정점집위정점집,약원도중량점적거리불대우2칙련이변소성적도.본문학정료권적평방도적색수.대우외부평면도,득도이하결론:설G시일개최대도위Δ(G)적간단련통외부평면도,G≠C5.칙χ(G2)≤Δ(G)+2.
The square of a graph G, denoted by G2, is a graph with the same vertex set such that two vertices are adjacent in G2 iff their distance is at most 2 in G. In this article we determine the chromatic number of the square of cycles. For outerplanar graphs we get the following main result: Let G be a connected simple outerplanar graph with maximum degree Δ(G), G≠C5. Then χ(G2)≤Δ(G)+2.