Partitioning edge-coloured complete graphs into monochromatic cycles期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Partitioning edge-coloured complete graphs into monochromatic cycles

Affiliation:	1. Department of Mathematics and Statistics, McGill University, Montréal, Canada;2. School of Computer Science, McGill University, Montréal, Canada;3. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, China

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.

Keywords:	Ramsey Theory graph partitioning cycles in graphs
本文献已被 ScienceDirect 等数据库收录！