Galvin's bipartite list-edge-colouring theorem

From Egres Open
Jump to: navigation, search

Theorem (Galvin [1]). The list-edge-colouring number of a bipartite graph is equal to its maximum degree.

Vizing [2] conjectures that for any graph the list-edge-colouring number equals the edge-colouring number. For details on this conjecture, see the Open Problem Garden. A more general conjecture of Gravier and Maffray [3] is that the list-colouring number of a claw-free graph is always equal to its chromatic number. A proof of this for perfect graphs would generalize Galvin's theorem; currently it is known only for perfect graphs of clique number at most 4 [4].


  1. F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63(1) (1995), 153-158, DOI link, pdf link
  2. V. G. Vizing, The chromatic class of a multigraph, Cybernetics and Systems Analysis 1 (1965), 32-41. DOI link.
  3. S. Gravier, F. Maffray, Graphs whose choice number is equal to their chromatic number, ACM link
  4. S. Gravier, F. Maffray, L. Pastor, On the choosability of claw-free perfect graphs, arXiv link