Feedback

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, M., Kemnitz, A., 2018. A Note on Not-4-List Colorable Planar Graphs. https://doi.org/10.37236/7320
Could not load citation form. Default citation form is displayed.

Access Statistic

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

Rights

Use and reproduction:

Export