Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652162 | Electronic Notes in Discrete Mathematics | 2013 | 7 Pages |
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 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics