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 - mstein@dim.uchile.cl
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.