Polychromatic colorings of bounded degree plane graphs
Polychromatic colorings of bounded degree plane graphs
复制标题
有界度平面图的多色着色
DOI：
10.1002/jgt.20357
复制
发表时间：
2009
影响因子：
0.9
通讯作者：
Roi Krakovski
中科院分区：
文献类型：
--
作者：
Elad Horev;Roi Krakovski
平面图G的多色k -着色是对G的顶点分配k种颜色，使得G的每个面在其边界上都有k种颜色。对于给定的平面图G，求最大k，使得G允许多色k‐着色。本文证明了除K4或K4在5个顶点上的细分外，每一个至少为3阶且最大为3阶的连通平面图都允许正则意义上的3 -着色（即没有单色边），并且也是多色3 -着色。我们的证明是建设性的，并暗示了一个多项式时间算法。©2009 Wiley期刊公司[J] .图论学报，2009,31 (4):998 - 998
A polychromatic k‐coloring of a plane graph G is an assignment of k colors to the vertices of G such that every face of G has all k colors on its boundary. For a given plane graph G, one seeks the maximum number k such that G admits a polychromatic k ‐coloring. In this paper, it is proven that every connected plane graph of order at least three, and maximum degree three, other than K4 or a subdivision of K4 on five vertices, admits a 3‐coloring in the regular sense (i.e., no monochromatic edges) that is also a polychromatic 3‐coloring. Our proof is constructive and implies a polynomial‐time algorithm. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 269‐283, 2009