Vertex covering with monochromatic pieces of few colours (Q1671656): Difference between revisions

Summary: In [Math. Pannonica 6, No. 1, 7--10 (1995; Zbl 0828.05040)], \textit{P. Erdős} and \textit{A. Gyárfás} proved that in every \(2\)-colouring of the edges of \(K_n\), there is a vertex cover by \(2\sqrt{n}\) monochromatic paths of the same colour, which is optimal up to a constant factor. The main goal of this paper is to study the natural multi-colour generalization of this problem: given two positive integers \(r,s\), what is the smallest number \(pc_{r,s}(K_n)\) such that in every colouring of the edges of \(K_n\) with \(r\) colours, there exists a vertex cover of \(K_n\) by \(pc_{r,s}(K_n)\) monochromatic paths using altogether at most \(s\) different colours? For fixed integers \(r > s\) and as \(n\to\infty\), we prove that \(pc_{r,s} (K_n) = \Theta(n^{1/\chi})\), where \(\chi=\max\{1,2+2s-r\}\) is the chromatic number of the Kneser graph \(\mathcal{KG}(r,r-s)\). More generally, if one replaces \(K_n\) by an arbitrary \(n\)-vertex graph with fixed independence number \(\alpha\), then we have \(pc_{r,s}(G) = O(n^{1/\chi)}\), where this time around \(\chi\) is the chromatic number of the Kneser hypergraph \(\mathcal{KG}^{(\alpha+1)}(r, r-s)\). This result is tight in the sense that there exist graphs with independence number \(\alpha\) for which \(pc_{r,s}(G)=\Omega(n^{1/\chi})\). This is in sharp contrast to the case \(r=s\), where it follows from a result of \textit{G. N. Sárkőzy} [J. Graph Theory 66, No. 1, 57--64 (2011; Zbl 1222.05075)] that \(pc_{r,r}(G)\) depends only on \(r\) and \(\alpha\), but not on the number of vertices. We obtain similar results for the situation where instead of using paths, one wants to cover a graph with bounded independence number by monochromatic cycles, or a complete graph by monochromatic \(d\)-regular graphs.