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.
@article{10_37236_7320,
author = {Margit Voigt and Arnfried Kemnitz},
title = {A note on not-4-list colorable planar graphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {2},
doi = {10.37236/7320},
zbl = {1388.05048},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7320/}
}
TY - JOUR
AU - Margit Voigt
AU - Arnfried Kemnitz
TI - A note on not-4-list colorable planar graphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/7320/
DO - 10.37236/7320
ID - 10_37236_7320
ER -
%0 Journal Article
%A Margit Voigt
%A Arnfried Kemnitz
%T A note on not-4-list colorable planar graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7320/
%R 10.37236/7320
%F 10_37236_7320
Margit Voigt; Arnfried Kemnitz. A note on not-4-list colorable planar graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/7320
