Planar 3-colorability is polynomial complete

Montassier et al. showed that every planar graph without cycles of length at most five at distance less than four is 3-colorable [A relaxation of of Havel's 3-color problem, Inform. Process. Lett. 107 (2008) 107---109]. Borodin, Montassier and Raspaud ...

A graph G is called (d 1 , … , d r)-colorable if its vertex set can be partitioned into r sets V 1 , … , V r such that the maximum degree of the induced subgraph G [ V i ] of G is at most d i for i ∈ { 1 , … , r }. Steinberg ...

Let d"1,d"2,...,d"k be k non-negative integers. A graph G is (d"1,d"2,...,d"k)-colorable, if the vertex set of G can be partitioned into subsets V"1,V"2,...,V"k such that the subgraph G[V"i] induced by V"i has maximum degree at most d"i for i=1,2,...,k. ...