TITLE
Linear-time algorithms to color topological graphs
AUTHOR
Warren D. Smith
ABSTRACT
We describe a linear-time algorithm for
4-coloring planar graphs.
We indeed give an $O(V+E+|\chi|+1)$-time
algorithm to $C$-color $V$-vertex $E$-edge graphs
embeddable on a 2-manifold $M$ of Euler characteristic $\chi$
where $C(M)$ is given by Heawood's (minimax optimal) formula.
Finally, there is a linear-time algorithm to 5-color a graph embedded
on any fixed surface $M$ \emph{except} that an $M$-dependent constant number
of vertices are left uncolored.
All the algorithms are simple and practical and run on a deterministic
pointer machine, except
for planar graph 4-coloring which involves enormous constant factors and requires
an integer RAM with a random number generator.
All of the algorithms mentioned so far are in the ultra-parallelizable deterministic
computational complexity class ``NC.''
We also have more practical planar 4-coloring algorithms that can run on
pointer machines in $O(V \log V)$ randomized time and $O(V)$ space,
and a very simple $O(V)$-time
coloring algorithm for planar graphs which conjecturally uses 4 colors.