×

A Grötzsch-type theorem for list colourings with impropriety one. (English) Zbl 0941.05027

The \((L,d)\)-colouring is a mapping \(f\), which assigns to each vertex \(v\in V(G)\) a colour \(f(v)\) from a list \(L(v)\) of colours so that \(v\) has at most \(d\) neighbours coloured with \(f(v)\). For \(m\in N\), the graph \(G\) is \((m,d)\)-choosable, if there exists an \((L,d)\)-colouring for every list assignment \(L\) with \(|L(v)|\geq m\) for each \(v\in V(G)\). The author proves the following Grötzsch-type theorem. Every triangle-free planar graph \(G\) is \((3,1)\)-choosable, and if \(G\) has a \(4\)- or \(5\)-cycle \(C\), then every \((L,1)\)-colouring of \(C\) can be extended to an \((L,1)\)-colouring of \(G\). The \((m,d)\)-choosability of all triangle-free (outer)planar graphs is established, too.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI