List improper colorings of planar graphs with prescribed girth Original Research Article

A graph G is m-choosable with impropriety d, or simply (m,d)∗-choosable, if for every list assignment L, where |L(v)|⩾m for every v∈V(G), there exists an L-coloring of G such that every vertex of G has at most d neighbors colored with the same color as itself. Denote by gd the smallest number such that every planar graph of girth at least gd is (2,d)∗-choosable. In this paper it is shown that g1⩽9, g2⩽7, g3⩽6 and gd=5 for every d⩾4.