Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: list total colouring

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Some totally 4-choosable multigraphs

100%

Woodall D.

Discussiones Mathematicae Graph Theory

2007

tom 27

nr 3

425-455

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Woodall D.

1 2007

Wyniki wyszukiwania

Some totally 4-choosable multigraphs