【摘要】 图G的平方图,记作G2,是一个以原图的顶点集作为顶点集,若原图中两点的距离不大于2则连以边所成的图.图G的列表染色数,记作lχ(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在G顶点的一个正常染色.设G是一个最大度为Δ(G)的2-连通外部平面图,则lχ(G2)≤Δ(G)+2.更多还原

【Abstract】 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.The list chromatic number of a graph G,denoted by χl(G) is the minimum number k such that if we give a list of k colors to each vertex of G,there is a vertex proper coloring of G where each vertex receives a color from its own list. Let G be a 2-connecded outerplanar graph with maximum degree Δ(G),then χl(G2)≤Δ(G)+2.更多还原