Coloring the square of a planar graph
Coloring the square of a planar graph
复制标题
DOI：
10.1002/jgt.10077
复制
发表时间：
2003-02
影响因子：
0.9
通讯作者：
J. V. D. Heuvel;Sean McGuinness
中科院分区：
文献类型：
--
作者：
J. V. D. Heuvel;Sean McGuinness
我们证明，对于任何最大度为Δ的平面图G，G的平方的色数满足χ(G²) ≤ 2Δ + 25。我们将这一结果推广到平面图的整数标记问题上，该问题涉及图中距离为1和2的约束条件。© 2002威利期刊公司。《图论杂志》42卷：110 - 124页，2003年
We prove that for any planar graph G with maximum degree Δ, it holds that the chromatic number of the square of G satisfies χ(G2) ≤ 2Δ + 25. We generalize this result to integer labelings of planar graphs involving constraints on distances one and two in the graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 110–124, 2003