Date:
Mon, 30/12/201910:00-12:00
Location:
C-400, CS building
Speaker: Gal Kronenberg (Oxford)
Title: The chromatic index of random multigraphs
Abstract:
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)≥Δ. 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). We say that a multigraph is first class if the upper bound for the chromatic index matches the trivial lower bound of max{Δ,ρ(G)}, that is, if χ'(G) = max{Δ,ρ(G)}. In the 70s, Goldberg, and independently Seymour, conjectured that for any multigraph G, χ'(G) ≤ max{Δ+1,ρ(G)}. We show that their conjecture (in a stronger form) is true for random multigraphs, and that a typical multigraph is, in fact, first class.
Joint work with Penny Haxell and Michael Krivelevich.