@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:
Color u with the color in L(u) and color v with the color in L(v).
Base case: |T| = |C| = 3, color o in C - {u,v} with one of the colors in L(o) - L(u) - L(v).
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'.
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.
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:
Color u with the color in L(u) and color v with the color in L(v).
Base case: |T| = |C| = 3, color o in C - {u,v} with one of the colors in L(o) - L(u) - L(v).
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'.
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.