Defective choosability results for outerplanar and related graphs (Q1850061): Difference between revisions

It is known that if every vertex \(v\) of an outerplanar graph \(G\) is given a list \(L(v)\) of at least two colors, then \(G\) has an \((L,2)^{*}\)-coloring; that is, one can color each vertex with a color from its own list so that no vertex has more than two neighbours with the same color as itself. In this paper it is proved that if, in addition, \(|L(u)\cap L(v)|\leq 1\) for each edge \(uv\), or \(|L(u)\cup L(v)|\geq 4\) for each edge \(uv\), then \(G\) has an \((L,1)^{*}\)-coloring, and if \(|L(u)\cup L(v)|\geq 5\) for each edge \(uv\) then \(G\) has an \((L,0)^{*}\)-coloring (a proper \(L\)-coloring). All possible choosability results of these types for outerplanar graphs, \(K_{2,3}\)-minor-free graphs and \(K_{4}\)-minor-free graphs are also described here.