Edge and total choosability of near-outerplanar graphs

Hetherington, T.J. and Woodall, D.R., 2006. Edge and total choosability of near-outerplanar graphs. Electronic Journal of Combinatorics, 13 (98).

193235_1615 Hetherington Publisher.pdf

Download (105kB) | Preview


It is proved that, if G is a K4-minor-free graph with maximum degree ∆ ≥ 4, then G is totally (∆ + 1)-choosable; that is, if every element (vertex or edge) of G is assigned a list of ∆ + 1 colours, then every element can be coloured with a colour from its own list in such a way that every two adjacent or incident elements are coloured with different colours. Together with other known results, this shows that the List-Total-Colouring Conjecture, that ch’’(G) = χ’(G) for every graph G, is true for all K4-minor-free graphs. The List-Edge-Colouring Conjecture is also known to be true for these graphs. As a fairly straightforward consequence, it is proved that both conjectures hold also for all K2,3-minor free graphs and all ( K2 + (K1 U K2))-minor-free graphs.

Item Type: Journal article
Publication Title: Electronic Journal of Combinatorics
Creators: Hetherington, T.J. and Woodall, D.R.
Publisher: International Press
Date: 2006
Volume: 13
Number: 98
Divisions: Schools > School of Science and Technology
Record created by: EPrints Services
Date Added: 09 Oct 2015 09:54
Last Modified: 19 Oct 2015 14:24
URI: https://irep.ntu.ac.uk/id/eprint/4691

Actions (login required)

Edit View Edit View


Views per month over past year


Downloads per month over past year