ArticleOriginal scientific text

Title

Some totally 4-choosable multigraphs

Authors 1

Affiliations

  1. School of Mathematical Sciences, University of Nottingham, Nottingham NG7 2RD, UK

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.

Keywords

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

Bibliography

  1. N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992) 125-134, doi: 10.1007/BF01204715.
  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.
  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.
  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. 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. M. Juvan, B. Mohar and R. Skrekovski, List total colourings of graphs, Combin. Probab. Comput. 7 (1998) 181-188, doi: 10.1017/S0963548397003210.
  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.
  8. V.G. Vizing, Colouring the vertices of a graph in prescribed colours (in Russian), Metody Diskret. Analiz. 29 (1976) 3-10.
  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.
  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.
Pages:
425-455
Main language of publication
English
Received
2006-04-21
Accepted
2007-07-06
Published
2007
Exact and natural sciences