English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In 1995, Erd\H{o}s and Gy\'arf\'as proved that in every $2$-colouring of theedges of $K_n$, there is a vertex cover by $2\sqrt{n}$ monochromatic paths ofthe same colour, which is optimal up to a constant factor. The main goal ofthis paper is to study the natural multi-colour generalization of this problem:given two positive integers $r,s$, what is the smallest number$\text{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 $\text{pc}_{r,s}(K_n)$monochromatic paths using altogether at most $s$ different colours? For fixedintegers $r>s$ and as $n\to\infty$, we prove that $\text{pc}_{r,s}(K_n) =\Theta(n^{1/\chi})$, where $\chi=\max{\{1,2+2s-r\}}$ is the chromatic number ofthe Kneser gr aph $\text{KG}(r,r-s)$. More generally, if one replaces $K_n$ byan arbitrary $n$-vertex graph with fixed independence number $\alpha$, then wehave $\text{pc}_{r,s}(G) = O(n^{1/\chi})$, where this time around $\chi$ is thechromatic number of the Kneser hypergraph $\text{KG}^{(\alpha+1)}(r,r-s)$. Thisresult is tight in the sense that there exist graphs with independence number$\alpha$ for which $\text{pc}_{r,s}(G) = \Omega(n^{1/\chi})$. This is in sharpcontrast to the case $r=s$, where it follows from a result of S\'ark\"ozy(2012) that $\text{pc}_{r,r}(G)$ depends only on $r$ and $\alpha$, but not onthe number of vertices. We obtain similar results for the situation whereinstead of using paths, one wants to cover a graph with bounded independencenumber by monochromatic cycles, or a complete graph by monochromatic$d$-regular graphs.

Vertex covering with monochromatic pieces of few colours