Hostname: page-component-7bb8b95d7b-pwrkn Total loading time: 0 Render date: 2024-09-06T09:43:48.905Z Has data issue: false hasContentIssue false
  • English
  • Français

Short Proof of Galvin's Theorem on the List-chromatic Index of a Bipartite Multigraph

Published online by Cambridge University Press:  12 September 2008

Tomaž Slivnik
Tomaž Slivnik
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, UK
Get access Rights & Permissions [Opens in a new window]

Abstract

Recently, Galvin [7] proved that every k-edge-colourable bipartite multigraph is k-edge-choosable. In particular, for a bipartite multigraph G, . Here we give a brief self-contained proof of this result.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 1 , March 1996 , pp. 91 - 94
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Alon, N. and Tarsi, M. (1992) Colorings and orientations of graphs. Combinatorica 12 (2) 125–134.CrossRefGoogle Scholar
[2]Bollobás, B. and Harris, A. J. (1985) List-colourings of graphs. Graphs and Combinatorics 1 115–127.CrossRefGoogle Scholar
[3]Bollobás, B. and Hind, H. R. (1989) A new upper bound for the list chromatic number. Discrete Mathematics 74 65–75.CrossRefGoogle Scholar
[4]Chetwynd, A. and Häggkvist, R. (1989) A note on list-colorings. J. Graph Theory 13 87–95.CrossRefGoogle Scholar
[5]Erdős, P., Rubin, A. L. and Taylor, H. (1980) Choosability in graphs. Congressus Numerantium 26 125–157.Google Scholar
[6]Gabow, H. N. (1976) Using Euler partitions to edge colour bipartite multigraphs. Int. J. Comput. Infor. Sci. 5 345–355.CrossRefGoogle Scholar
[7]Galvin, F. (1995) The list chromatic index of a bipartite multigraph. J. Combinatorial Theory Series B 63 153–158.CrossRefGoogle Scholar
[8]Gale, D. and Shapley, L. S. (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69 9–15.CrossRefGoogle Scholar
[9]Häggkvist, R. and Janssen, J. (1993) On the list-chromatic index of bipartite graphs. Research Report No. 15, Department of Mathematics, University of Umeå.Google Scholar
[10]Häggkvist, R. and Janssen, J. (1993) New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs. Research Report No. 19, Department of Mathematics, University of Umeå.Google Scholar
[11]Harris, A. J. (1985) Problems and conjectures in extremal graph theory. PhD dissertation, Cambridge.Google Scholar
[12]Janssen, J. C. M. (1993) Even and odd latin squares. PhD dissertation, Lehigh University.Google Scholar
[13]Janssen, J. C. M. (1993) The Dinitz problem solved for rectangles. Bull. Amer. Math. Soc. (New Series) 29 243–249.CrossRefGoogle Scholar
[14]Kahn, J. (to appear) Asymptotically good list-colorings. J. Combinatorial Theory, Series A.Google Scholar
[15]Maffray, F. (1992) Kernels in perfect line-graphs. J. Combinatorial Theory, Series B 55 1–8.CrossRefGoogle Scholar
[16]Vizing, V. G. (1992) Colouring the vertices of a graph in prescribed colours (in Russian). Diskret. Analiz. 29 3–10.Google Scholar