×

zbMATH — the first resource for mathematics

List improper colourings of planar graphs. (English) Zbl 0940.05031
Summary: A graph \(G\) is \(m\)-choosable with impropriety \(d\), or simply \((m,d)^*\)-choosable, if for every list assignment \(L\), where \(|L(v)|\geq m\) for every \(v\in 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.

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI