Note on 3-Choosability of Planar Graphs with Maximum Degree 4

François Dross, Borut Lužar, Mária Maceková +1

Deciding whether a planar graph (even of maximum degree $4$) is $3$-colorable is NP-complete. Determining subclasses of planar graphs being $3$-colorable has a long history, but si…