A Note on Not-4-List Colorable Planar Graphs

Margit Voigt, Arnfried Kemnitz

Abstract


The Four Color Theorem states that every planar graph is properly 4-colorable. Moreover, it is well known that there are planar graphs that are non-$4$-list colorable. In this paper we investigate a problem combining proper colorings and list colorings. We ask whether the vertex set of every planar graph can be partitioned into two subsets where one subset induces a bipartite graph and the other subset induces a $2$-list colorable graph. We answer this question in the negative strengthening the result on non-$4$-list colorable planar graphs.

Keywords


List colouring; Planar graph

Full Text:

PDF