Coupled choosability of near-outerplanar graphs
Timothy J. Hetherington · Nottingham Trent University's Institutional Repository (Nottingham Trent Repository) · 2014
It is proved that if G is a plane embedding of a K4-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 elements 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 K2,3-minor-free graph or a (K¯2 + (K1 [ K2))-minor-free graph, then G is coupled 5-choosable. All results here are sharp, even for outerplane graphs.