Entire choosability of near-outerplane graphs

Hetherington, TJ, 2009. Entire choosability of near-outerplane graphs. Discrete Mathematics, 309 (8), pp. 2153-2165.

Preview

Text 200152_6539 Hetherington Preprint.pdf Download (487kB) | Preview

Abstract

It is proved that if G is a plane embedding of a K4-minor-free graph with maximum degree Δ, then G is entirely 7-choosable if Δ≤4 and G is entirely (Δ+ 2)-choosable if Δ≥ 5; that is, if every vertex, edge and face of G is given a list of 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 G is a plane embedding of a K2,3-minor-free graph or a (K2 + (K1 U K2))-minor-free graph. As a special case this proves that the Entire Colouring Conjecture, that a plane graph is entirely (Δ + 4)-colourable, holds if G is a plane embedding of a K4-minor-free graph, a K2,3-minor-free graph or a (K2 + (K1 U K2))-minor-free graph.

Item Type:	Journal article
Publication Title:	Discrete Mathematics
Creators:	Hetherington, T.J.
Publisher:	Elsevier
Date:	2009
Volume:	309
Number:	8
Identifiers:	Number Type 10.1016/j.disc.2008.04.043 DOI
Rights:	Copyright © 2009 Elsevier B.V. All rights reserved.
Divisions:	Schools > School of Science and Technology
Record created by:	EPrints Services
Date Added:	09 Oct 2015 10:12
Last Modified:	23 Aug 2016 09:08
URI:	https://irep.ntu.ac.uk/id/eprint/9378

Actions (login required)

Edit View

Statistics

Views

Downloads