Pokrovskiy, A;
(2014)
Partitioning edge-coloured complete graphs into monochromatic cycles and paths.
Journal of Combinatorial Theory, Series B
, 106
pp. 70-97.
10.1016/j.jctb.2014.01.003.
Preview |
Text
PathsCounterexample2013.pdf - Accepted Version Download (528kB) | Preview |
Abstract
A conjecture of Erdős, Gyárfás, and Pyber says that in any edge-colouring of a complete graph with r colours, it is possible to cover all the vertices with r vertex-disjoint monochromatic cycles. So far, this conjecture has been proven only for . In this paper we show that in fact this conjecture is false for all . In contrast to this, we show that in any edge-colouring of a complete graph with three colours, it is possible to cover all the vertices with three vertex-disjoint monochromatic paths, proving a particular case of a conjecture due to Gyárfás. As an intermediate result we show that in any edge-colouring of the complete graph with the colours red and blue, it is possible to cover all the vertices with a red path, and a disjoint blue balanced complete bipartite graph.
| Type: | Article |
|---|---|
| Title: | Partitioning edge-coloured complete graphs into monochromatic cycles and paths |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.jctb.2014.01.003 |
| Publisher version: | https://doi.org/10.1016/j.jctb.2014.01.003 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Graph partitioning, Ramsey theory |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10112667 |
Archive Staff Only
 |
View Item |
