Short proof of Galvin’s theorem on the list-chromatic index of a bipartite multigraph. (English) Zbl 0857.05034

Slivnik, Tomaž

Comb. Probab. Comput. 5, No. 1, 91-94 (1996).

The author gives a brief self-contained proof of a result by F. Galvin [J. Comb. Theory, Ser. B 63, No. 1, 153-158 (1995; Zbl 0826.05026)] saying that in every bipartite multigraph the list chromatic index equals the chromatic index.

Reviewer: D.Cvetković (Beograd)

MSC:

05C15

Coloring of graphs and hypergraphs

Keywords:

Galvin’s theorem; bipartite multigraph; list chromatic index; chromatic index

References:

[1]	DOI: 10.1002/jgt.3190130112 · Zbl 0674.05026 · doi:10.1002/jgt.3190130112
[2]	DOI: 10.1016/0012-365X(89)90199-4 · Zbl 0674.05027 · doi:10.1016/0012-365X(89)90199-4
[3]	DOI: 10.1007/BF02582936 · Zbl 0606.05027 · doi:10.1007/BF02582936
[4]	DOI: 10.1007/BF01204715 · Zbl 0756.05049 · doi:10.1007/BF01204715
[5]	Vizing, Diskret. Analiz. 29 pp 3– (1992)
[6]	DOI: 10.1016/0095-8956(92)90028-V · Zbl 0694.05054 · doi:10.1016/0095-8956(92)90028-V
[7]	Erd?s, Congressus Numerantium 26 pp 125– (1980)
[8]	DOI: 10.1090/S0273-0979-1993-00430-0 · Zbl 0792.05053 · doi:10.1090/S0273-0979-1993-00430-0
[9]	Häggkvist, On the list-chromatic index of bipartite graphs (1993)
[10]	Häggkvist, New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs (1993)
[11]	DOI: 10.2307/2312726 · Zbl 0109.24403 · doi:10.2307/2312726
[12]	DOI: 10.1006/jctb.1995.1011 · Zbl 0826.05026 · doi:10.1006/jctb.1995.1011
[13]	DOI: 10.1007/BF00998632 · Zbl 0411.05039 · doi:10.1007/BF00998632
[14]	Kahn, J. Combinatorial Theory