List Improper Colourings of Planar Graphs

Source abstract

A graph G is m -choosable with impropriety d , or simply ( m , d )*-choosable, if for every list assignment L , where [mid ] L ( v )[mid ][ges ] m for every v ∈ V ( G ), there exists an L -colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We show that every planar graph is (3, 2)*-choosable and every outerplanar graph is (2, 2)*-choosable. We also propose some interesting problems about this colouring.