Gal Kronenberg

Tel Aviv University

The chromatic index of random multigraphs

For a (multi)graph G=(V,E), we denote by χ'(G) the minimum number of colors needed to color the edges of G properly. Clearly, Δ≤χ'(G). Vizing proved that χ'(G)≤ Δ(G)+μ(G), where μ(G) is the maximum edge multiplicity of G. Let S⊆V and let ρ(G)=max{ e(S)/ \floor{|S|/2} | S⊆V }. By the fact that every color class forms a matching, we have that χ'(G)≥ρ(G). In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph G, χ'(G)ϵ{Δ, Δ+1,ρ(G)}. We show that their conjecture (in a stronger form) is true for random multigraphs.

Let M(n,m) be the collection of all multigraphs with n vertices and m edges. Our result states that, for a given m:=m(n), almost all multigraphs in M(n,m) satisfy χ'(G)=max{Δ,ρ(G)}. In particular, we show that if n is even and m:=m(n), then χ'(M)=Δ(M) for a typical M~M(n,m). Furthermore, for a fixed ε >0, if n is odd, then a typical M~M(n,m) has χ'(M)=Δ for m≤(1- ε)n^3\log n, and for m≥(1+ ε)n^3\log n, a typical M~M(n,m) has χ'(M)=ρ(M).

Joint work with Penny Haxell and Michael Krivelevich.