# Galvin's bipartite list-edge-colouring theorem

From Egres Open

**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]}.

## References

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