Some totally 4-choosable multigraphs

Woodall, Douglas

Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 425-455

Résumé

It is proved that if G is multigraph with maximum degree 3, and every submultigraph of G has average degree at most 2(1/2) and is different from one forbidden configuration C⁺₄ with average degree exactly 2(1/2), then G is totally 4-choosable; that is, if every element (vertex or edge) of G is assigned a list of 4 colours, then every element can be coloured with a colour from its own list in such a way that no two adjacent or incident elements are coloured with the same colour. This shows that the List-Total-Colouring Conjecture, that ch”(G) = χ”(G) for every multigraph G, is true for all multigraphs of this type. As a consequence, if G is a graph with maximum degree 3 and girth at least 10 that can be embedded in the plane, projective plane, torus or Klein bottle, then ch”(G) = χ”(G) = 4. Some further total choosability results are discussed for planar graphs with sufficiently large maximum degree and girth.

Détail

Keywords: maximum average degree, planar graph, total choosability, list total colouring