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 $({\overline{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.