Some totally 4-choosable multigraphs

Douglas R. Woodall

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 3, page 425-455
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Douglas R. Woodall. "Some totally 4-choosable multigraphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 425-455. <http://eudml.org/doc/270317>.

@article{DouglasR2007,
abstract = {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.},
author = {Douglas R. Woodall},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {maximum average degree; planar graph; total choosability; list total colouring},
language = {eng},
number = {3},
pages = {425-455},
title = {Some totally 4-choosable multigraphs},
url = {http://eudml.org/doc/270317},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Douglas R. Woodall
TI - Some totally 4-choosable multigraphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 425
EP - 455
AB - 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.
LA - eng
KW - maximum average degree; planar graph; total choosability; list total colouring
UR - http://eudml.org/doc/270317
ER -

References

top
  1. [1] N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125-134, doi: 10.1007/BF01204715. Zbl0756.05049
  2. [2] O.V. Borodin, A.V. Kostochka and D.R. Woodall, List edge and list total colourings of multigraphs, J. Combin. Theory (B) 71 (1997) 184-204, doi: 10.1006/jctb.1997.1780. Zbl0876.05032
  3. [3] O.V. Borodin, A.V. Kostochka and D.R. Woodall, Total colourings of planar graphs with large girth, European J. Combin. 19 (1998) 19-24, doi: 10.1006/eujc.1997.0152. Zbl0886.05065
  4. [4] A. Chetwynd, Total colourings of graphs, in: R. Nelson and R.J. Wilson, eds, Graph Colourings (Milton Keynes, 1988), Pitman Res. Notes Math. Ser. 218 (Longman Sci. Tech., Harlow, 1990) 65-77. 
  5. [5] P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, 1979, Congr. Numer. 26 (1980) 125-157. 
  6. [6] M. Juvan, B. Mohar and R. Skrekovski, List total colourings of graphs, Combin. Probab. Comput. 7 (1998) 181-188, doi: 10.1017/S0963548397003210. Zbl0911.05033
  7. [7] L. Lovász, Three short proofs in graph theory, J. Combin. Theory (B) 19 (1975) 269-271, doi: 10.1016/0095-8956(75)90089-1. Zbl0322.05142
  8. [8] V.G. Vizing, Colouring the vertices of a graph in prescribed colours (in Russian), Metody Diskret. Analiz. 29 (1976) 3-10. 
  9. [9] W. Wang, Total chromatic number of planar graphs with maximum degree 10, J. Graph Theory 54 (2007) 91-102, doi: 10.1002/jgt.20195. Zbl1110.05037
  10. [10] D.R. Woodall, List colourings of graphs, in: J.W.P. Hirschfeld, ed., Surveys in Combinatorics, 2001, London Math. Soc. Lecture Note Ser. 288 (Cambridge Univ. Press, Cambridge, 2001) 269-301. Zbl0979.05047

NotesEmbed ?

top

You must be logged in to post comments.