Coupled Choosability of Near-Outerplane Graphs

Abstract

It is proved that if \(G\) is a plane embedding of a \(K_4\)-minor-free graph, then \(G\) is coupled \(5\)-choosable; that is, if every vertex and every face of \(G\) is given a list of \(5\) colours, then each of these ele-ments can be given a colour from its list such that no two adjacent or incident elements are given the same colour. Using this result it is proved also that if \(G\) is a plane embedding of a \(K_{2,3}\),\(3\)-minor-free graph or a \((\bar{K}_2 + (K_1 \cup K_2))\)-minor-free graph, then \(G\) is coupled \(5\)-choosable. All results here are sharp, even for outerplane graphs.