A Linear-Time Algorithm for 7-Coloring 1-Plane Graphs |
| |
Authors: | Zhi-Zhong Chen Mitsuharu Kouno |
| |
Affiliation: | (1) Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, Saitama 350-0394, Japan |
| |
Abstract: | 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 does not lead to a linear-time algorithm. This paper presents a linear-time algorithm for 7-coloring 1-plane graphs (which are 1-planar graphs 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 structural lemma that may be 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. |
| |
Keywords: | Planar graphs Plane embeddings Planar graphs Plane embeddings Graph algorithms Vertex coloring NP-completeness |
本文献已被 SpringerLink 等数据库收录! |