  In 1994, Thomassen proved that every planar graph is 5-list-colorable. In
1995, Thomassen proved that every planar graph of girth at least five is
3-list-colorable. His proofs naturally lead to quadratic-time algorithms to
find such colorings. Here, we provide the first such linear-time algorithms to
find such colorings.
  For a fixed surface S, Thomassen showed in 1997 that there exists a
linear-time algorithm to decide if a graph embedded in S is 5-colorable and
similarly in 2003 if a graph of girth at least five embedded in S is
3-colorable. Using the theory of hyperbolic families, the author and Thomas
showed such algorithms exist for list-colorings. Dvorak and Kawarabayashi
actually gave an $O(n^{O(g+1)})$-time algorithm to find such colorings (if they
exist) in n-vertex graphs where g is the Euler genus of the surface. Here we
provide the first such algorithm whose exponent does not depend on the genus;
indeed, we provide a linear-time algorithm.
  In 1988, Goldberg, Plotkin and Shannon provided a deterministic distributed
algorithm for 7-coloring n-vertex planar graphs in $O(\log n)$ rounds. In 2018,
Aboulker, Bonamy, Bousquet, and Esperet provided a deterministic distributed
algorithm for 6-coloring n-vertex planar graphs in $O(\log^3 n)$ rounds. Their
algorithm in fact works for 6-list-coloring. They also provided an $O(\log^3
n)$-round algorithm for 4-list-coloring triangle-free planar graphs. Chechik
and Mukhtar independently obtained such algorithms for ordinary coloring in
$O(\log n)$ rounds, which is best possible in terms of running time. Here we
provide the first polylogarithmic deterministic distributed algorithms for
5-coloring n-vertex planar graphs and similarly for 3-coloring planar graphs of
girth at least five. Indeed, these algorithms run in $O(\log n)$ rounds, work
also for list-colorings, and even work on a fixed surface (assuming such a
coloring exists).
