Article ID Journal Published Year Pages File Type
4649740 Discrete Mathematics 2009 13 Pages PDF
Abstract

It is proved that if GG is a plane embedding of a K4K4-minor-free graph with maximum degree ΔΔ, then GG is entirely 7-choosable if Δ≤4Δ≤4 and GG is entirely (Δ+2)(Δ+2)-choosable if Δ≥5Δ≥5; that is, if every vertex, edge and face of GG is given a list of max{7,Δ+2}max{7,Δ+2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if GG is a plane embedding of a K2,3K2,3-minor-free graph or a (K2̄+(K1∪K2))-minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (Δ+4)(Δ+4)-colourable, holds if GG is a plane embedding of a K4K4-minor-free graph, a K2,3K2,3-minor-free graph or a (K2̄+(K1∪K2))-minor-free graph.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,