- Tytuł:
- Some totally 4-choosable multigraphs
- Autorzy:
- Woodall, Douglas
- Powiązania:
- https://bibliotekanauki.pl/articles/743409.pdf
- Data publikacji:
- 2007
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
maximum average degree
planar graph
total choosability
list total colouring - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 425-455
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł