On Wednesday, 28.02.2018, at 16:15 in Arnimallee 3, SR 210
Penny Haxell (University of Waterloo)
will give a talk on
Chromatic index of random multigraphs
Let $G$ be a loopless multigraph with maximum degree $d$. It is clear that $d$ is a lower bound for the chromatic index of $G$ (the smallest $k$ such that $E(G)$ can be partitioned into $k$ matchings). A long-standing conjecture due to Goldberg and (independently) Seymour states that the chromatic index of $G$ takes one of only three possible values: $d$, $d+1$ or a certain other parameter of $G$, that is closely related to the fractional chromatic index of $G$ (and is also a natural lower bound for the chromatic index). Here we prove this conjecture for random multigraphs. In fact we prove the stronger statement that the value $d+1$ is not necessary for the random case. We will discuss various graph theoretical tools used in the proof, in particular the method of Tashkinov trees (which has been a key component of much of the progress on this conjecture to date).
This represents joint work with Michael Krivelevich and Gal Kronenberg.