FoCM 2014 conference

Workshop A4 - Graph Theory and Combinatorics

December 11, 15:30 ~ 16:00 - Room B11

Monochromatic path/cycle partitions

Maya Stein

University of Chile, Chile   -

A conjecture of Gyárfás says that given any colouring with $r$ colours of the edges of the complete graph $K_n$ on $n$ vertices, there are $r$ disjoint monochromatic paths that induce a partition of $V(K_n)$. The conjecture is true for $r\leq3$. Replacing paths with cycles, it is known that in general, the number of cycles needed is greater than $r$, but can be bounded by a function of $r$. (Here, single vertices/edges count as cycles.) For $r=2$, it is known that $2$ paths/cycles suffice.

This talk gives an overview on the history of the problem. We then describe some recent results for bipartite and multipartite graphs, with fixed values of $r$. We also study variants of the problem for $r$-local colourings, and for $r$-mean colourings. The results mentioned are joint work with Conlon, with Lang, with Lang and Schaudt, and with Schaudt, respectively.

View abstract PDF