A Note on Not-4-List Colorable Planar Graphs

Voigt, Margit; Kemnitz, Arnfried

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.

Cite

Citation style:

Voigt, Margit / Kemnitz, Arnfried: A Note on Not-4-List Colorable Planar Graphs. 2018. EJC Electronic Journal of Combinatorics.

Access Statistic

Total:
Downloads:
Abtractviews:
Last 12 Month:
Downloads:
Abtractviews:

show details

Rights

Use and reproduction:

Export