List edge and list total colourings of multigraphs

O. V. Borodin, A. V. Kostochka, D. R. Woodall

Research output: Contribution to journalArticle

Abstract

This paper exploits the remarkable new method of Galvin (J. Combin. Theory Ser. B63(1995), 153-158), who proved that the list edge chromatic numberχ′list(G) of a bipartite multigraphGequals its edge chromatic numberχ′(G). It is now proved here that if every edgee=uwof a bipartite multigraphGis assigned a list of at least max{d(u),d(w)} colours, thenGcan be edge-coloured with each edge receiving a colour from its list. If every edgee=uwin an arbitrary multigraphGis assigned a list of at least max{d(u),d(w)}+⌊12min{d(u),d(w)}⌋ colours, then the same holds; in particular, ifGhas maximum degreeΔ=Δ(G) thenχ′list(G)≤⌊32Δ⌋. Sufficient conditions are given in terms of the maximum degree and maximum average degree ofGin order thatχ′list(G)=Δandχ″list(G)=Δ+1. Consequences are deduced for planar graphs in terms of their maximum degree and girth, and it is also proved that ifGis a simple planar graph andΔ≥12 thenχ′list(G)=Δandχ″list(G)=Δ+1.

Original languageEnglish (US)
Pages (from-to)184-204
Number of pages21
JournalJournal of Combinatorial Theory. Series B
Volume71
Issue number2
DOIs
StatePublished - Nov 1 1997
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'List edge and list total colourings of multigraphs'. Together they form a unique fingerprint.

  • Cite this