Combinatorics Probability Computing · 1999 · 110 citations · 10 references
Natural SciencesMathematicsColor TheoryCombinatoricsDiscrete MathematicsGraph AlgorithmsGraph ColoringGraph TheoryColoring Planar GraphsColoring TheoremsList ColoringPlanar Graph Algorithms
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.
10
Every Planar Graph Is 5-Choosable
Carsten Thomassen · Journal of Combinatorial Theory Series B · 1994 · 516 citations
List colourings of planar graphs
Margit Voigt · Discrete Mathematics · 2006 · 194 citations
Lenore Cowen, Wayne Goddard, C. Esther Jesurum · Journal of Graph Theory · 1997 · 131 citations