Vertex coverings by monochromatic cycles and trees (Q1174783): Difference between revisions

\textit{A. Gyárfás} [Irregularities of partitions, Pap. Meet., Fertod/Hung. 1986, Algorithms Comb. 8, 89-91 (1989; Zbl 0736.05062)] conjectured that if the edges of a complete graph \(K\) are colored with \(r\) colors then, for some function \(f\), the vertex set of \(K\) can be covered by at most \(f(r)\) vertex disjoint monochromatic paths. Allowing cycles to include single vertices and edges, the authors prove a stronger form of the conjecture: If the edges of a complete graph \(K\) are colored with \(r\) colors then the vertex set of \(K\) can be covered by at most \(cr^2\log r\) vertex disjoint monochromatic cycles. This result makes it possible to define, as a function of \(r\), the minimum number of monochromatic cycles (or paths or trees) needed to cover (or partition) the vertex set of any \(r\)-colored complete graph. The authors conjecture that the cycle partition number is \(r\) and that the tree partition number is \(r-1\) and prove these for the case \(r=3\).