Partitioning edge-coloured complete graphs into monochromatic cycles
Pokrovskiy, A.
(2013).
Partitioning edge-coloured complete graphs into monochromatic cycles.
Electronic Notes in Discrete Mathematics,
43, 311-317.
https://doi.org/10.1016/j.endm.2013.07.049
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 r=2. In this note we show that in fact this conjecture is false for all r⩾3. We also discuss some weakenings of this conjecture which may still be true.
| Item Type | Article |
|---|---|
| Copyright holders | © 2013 Elsevier B.V. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1016/j.endm.2013.07.049 |
| Date Deposited | 16 Sep 2013 |
| URI | https://researchonline.lse.ac.uk/id/eprint/52600 |
Explore Further
- https://www.scopus.com/pages/publications/84883324956 (Scopus publication)
- http://www.elsevier.com/locate/endm (Official URL)