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
