5-list-coloring of planar graphs

[make-github-pseudonymous-again]

Reference

@Article{thomassen1994every,
title={Every planar graph is 5-choosable},
author={Thomassen, Carsten},
journal={Journal of Combinatorial Theory Series B},
volume={62},
number={1},
pages={180--181},
year={1994},
publisher={Academic Press, Inc. Orlando, FL, USA}
}

Algorithm

Input:
A triangulation T with outer boundary cycle C,
two adjacent vertices on C named u and v
and color assignment L for T such that
L(u) = {1},
L(v) = {2},
|L(o)| >= 3 for o in C - {u, v}, and
|L(i)| >= 5 for i in T - C.

Output: A proper coloring of T.

Steps:

1. Color u with the color in L(u) and color v with the color in L(v).

2. Base case: |T| = |C| = 3, color o in C - {u,v} with one of the colors in L(o) - L(u) - L(v).

3. If there is a chord (s,t) of C then split C along this chord into two
   smaller cycles, given two strictly smaller triangulations A and B.
   Let A be the triangulation that contains (u,v).
   Recursively color B with L.
   This gives a color assigment to s and t of 1' and 2' respectively. Let L'(s) = 1'
   and L'(t) = 2' and L'(x) = L(x) for all other vertices in B.
   Recursively color B with L'.

4. There is no chord. Let t != v be the other vertex of C that is adjacent to u.
   Let L'(t) = L(t) - L(u). L'(t) contains at least 2 colors {x,y}.
   For all vertices f adjacent to t that are in T - C let L'(f) = L(f) - {x,y}.
   For all other vertices x of T let L'(x) = L(x).
   Recursively color T - {t} with L'.
   Let s != u (could be v) be the other adjacent vertex of t on C and x be its
   assigned color without loss of generality. Extend the coloring of T - {t} to a coloring of T
   by coloring t with y.