A Linear-Time Algorithm for 7-coloring 1-planar Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
Zhizhong Chen, Mitsuharu Kouno · Kyoto University Research Information Repository (Kyoto University) · 2004
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 an efficient algorithm.This paper presents a linear-time algorithm for 7-coloring 1-planar graphs.The main difficulty in the design of our algorithm comes ffom the fact that the class of 1-planar graphs is not closed under the operation of edge contraction.This difficulty is overco me by a structure lemma that may find useful in other problems on l-planar graphs.