Edge and total choosability of near-outerplanar graphs
The electronic journal of combinatorics, Tome 13 (2006)
It is proved that, if $G$ is a $K_4$-minor-free graph with maximum degree $\Delta \ge 4$, then $G$ is totally $(\Delta+1)$-choosable; that is, if every element (vertex or edge) of $G$ is assigned a list of $\Delta+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 ${\rm ch}"(G) = \chi"(G)$ for every graph $G$, is true for all $K_4$-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 $K_{2,3}$-minor free graphs and all $(\bar K_2 + (K_1 \cup K_2))$-minor-free graphs.
@article{10_37236_1124,
author = {Timothy J. Hetherington and Douglas R. Woodall},
title = {Edge and total choosability of near-outerplanar graphs},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1124},
zbl = {1115.05032},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1124/}
}
Timothy J. Hetherington; Douglas R. Woodall. Edge and total choosability of near-outerplanar graphs. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1124
Cité par Sources :