Combinatorics: Gal Kronenberg (Oxford)

Speaker: Gal Kronenberg (Oxford)

Title: 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)≥Δ. 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.


Mon, 30/12/2019 - 10:00 to 12:00


C-400, CS building