A note on non-4-list colorable planar graphs Artikel uri icon

Open Access

  • false

Peer Reviewed

  • true

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.

Veröffentlichungszeitpunkt

  • August 6, 2018