Research Seminar Combinatorics

                                         Next talk    

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.



Mailing list:

To subscribe to the mailing-list of the seminar, please follow this link:

Seminar calendar:

To add the .ics file of the calendar to your favorite calendar reader (that supports the ICal format), please follow this link:
ICal calendar.

To add the calendar feeds to your favorite feed reader, please follow this link:
Calendar feeds.


For any request, please send an e-mail to:


Schedule and abstracts 2017/2018

Schedule and abstracts 2016/2017

Schedule and abstracts 2015/2016

Schedule and abstracts 2014/2015

Schedule and abstracts 2013/2014

Schedule and abstracts 2012/2013

Schedule and abstracts 2011/2012

Schedule and abstracts 2010/2011

Schedule and abstracts 2009/2010