Entire choosability of near-outerplane graphs

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

[img]
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:
NumberType
10.1016/j.disc.2008.04.043DOI
Rights: Copyright © 2009 Elsevier B.V. All rights reserved.
Divisions: Schools > School of Science and Technology
Depositing User: EPrints Services
Date Added: 09 Oct 2015 10:12
Last Modified: 23 Aug 2016 09:08
URI: http://irep.ntu.ac.uk/id/eprint/9378

Actions (login required)

Edit View Edit View

Views

Views per month over past year

Downloads

Downloads per month over past year