Edge and total choosability of near-outerplanar graphs

Hetherington, TJ and Woodall, DR, 2006. Edge and total choosability of near-outerplanar graphs. Electronic Journal of Combinatorics, 13 (98).

Preview

Text 193235_1615 Hetherington Publisher.pdf Download (105kB) | Preview

Abstract

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

Statistics

Views

Downloads