2012/05/24 by Alexey Pokrovskiy, Pokrovskiy, Alexey · 1 citation
Computer Science · Engineering · Mathematics · #05C38 #05C55 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1205.5492
openalex publication_date 2012/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A conjecture of Erd Hos, Gy 'arf 'as, and Pyber says that in any\nedge-colouring of a complete graph with r colours, it is possible to cover all\nthe vertices with r vertex-disjoint monochromatic cycles. So far, this\nconjecture has been proven only for r = 2. In this paper we show that in fact\nthis conjecture is false for all r > 2. In contrast to this, we show that in\nany edge-colouring of a complete graph with three colours, it is possible to\ncover all the vertices with three vertex-disjoint monochromatic paths, proving\na particular case of a conjecture due to Gy 'arf 'as. As an intermediate result\nwe show that in any edge-colouring of the complete graph with the colours red\nand blue, it is possible to cover all the vertices with a red path, and a\ndisjoint blue balanced complete bipartite graph.\n