%0 Journal Article
%T 平面图的平方染色数的一个新上界<br>New upper bound on the chromatic number of the square of a planar graph
%A 朱海洋
%A 顾 毓
%A 吕新忠&lt
%A br&gt
%A ZHU Hai-yang
%A GU Yu
%A Lü Xin-zhong
%J 山东大学学报（理学版）
%D 2016
%R 10.6040/j.issn.1671-9352.0.2014.594
%X 摘要： 令V(G)、E(G)、Δ(G)和χ(G)分别为G的顶点集、边集、最大度和色数。图G的平方图,记为G2,指的是一个图满足条件:V(G2)=V(G),并且uv∈E(G2)当且仅当1≤dG(u,v)≤2。证明了若G是Δ(G)≤6且围长g(G)≥5的平面图,则χ(G2)≤Δ(G)+8。<br>Abstract: Let V(G), E(G), Δ(G) and χ(G) denote the vertex set, the edge set, the maximum degree and the chromatic number of a graph G, respectively. The square G2 of a graph G is defined such that V(G2)=V(G), and uv∈E(G2)if and only if 1≤dG(u,v)≤2. It is proved that χ(G2)≤Δ(G)+8 if G is a planar graph with Δ(G)≤6 and girth g(G)≥5
%K 平面图
%K 染色
%K 围长
%K 平方图
%K &lt
%K br&gt
%K planar graph
%K girth
%K coloring
%K squares
%U http://lxbwk.njournal.sdu.edu.cn/CN/10.6040/j.issn.1671-9352.0.2014.594