Edge and total choosability of near-outerplanar graphs
The electronic journal of combinatorics, Tome 13 (2006)
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
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.
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
@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/}
}
Cité par Sources :