A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs
A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs
复制标题
7 色 1 平面图的线性时间算法
DOI：
10.1007/978-3-540-45138-9_29
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Mitsuharu Kouno
中科院分区：
文献类型：
--
作者：
Zhi;Mitsuharu Kouno
如果图G能以每条边最多与另一条边相交的方式嵌入平面中，那么它就是平面的。Borodin证明了1-平面图是6色的，但他的证明只导致了一个复杂的多项式（但非线性）时间算法。本文提出了一种求解7色1-平面图（已嵌入平面）的线性时间算法。本算法设计的主要难点在于，在边收缩操作下，1-平面图类是不闭合的。这个困难是由一个结构引理克服的，这个引理可能在1-平面图上的其他问题中发现有用。本文还证明了判定给定的1-平面图是否为4色是np完全的。确定给定的1-平面图是否为5色问题的复杂性仍然是未知的。
A graph G is 1-planar if it can be embedded in the plane in such a way that each edge crosses at most one other edge. Borodin showed that 1-planar graphs are 6-colorable, but his proof only leads to a complicated polynomial (but nonlinear) time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-planar graphs (that are already embedded in the plane). The main difficulty in the design of our algorithm comes from the fact that the class of 1-planar graphs is not closed under the operation of edge contraction. This difficulty is overcome by a structure lemma that may find useful in other problems on 1-planar graphs. This paper also shows that it is NP-complete to decide whether a given 1-planar graph is 4-colorable. The complexity of the problem of deciding whether a given 1-planar graph is 5-colorable is still unknown.