Abstract of Paper

A Linear Time Algorithm For 7-Coloring 1-Planar Graphs
by Zhi-Zhong Chen, Mitsuharu Kouno

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 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
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.