The complexity of planar graph choosability

Abstract

A graph \(G\) is {\em \(k\)-choosable} if for every assignment of a set \(S(v)\) of \(k\) colors to every vertex \(v\) of \(G\), there is a proper coloring of \(G\) that assigns to each vertex \(v\) a color from \(S(v)\). We consider the complexity of deciding whether a given graph is \(k\)-choosable for some constant \(k\). In particular, it is shown that deciding whether a given planar graph is 4-choosable is NP-hard, and so is the problem of deciding whether a given planar triangle-free graph is 3-choosable. We also obtain simple constructions of a planar graph which is not 4-choosable and a planar triangle-free graph which is not 3-choosable.