Tools
Tools
Hetherington, T.J., 2009. Entire choosability of near-outerplane graphs. Discrete Mathematics, 309 (8), pp. 2153-2165.
|
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: |
|
||||
| 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 |
Views
Views per month over past year
Downloads
Downloads per month over past year
