Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.04704 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912943263711232 |
|---|---|
| author | Hawranick, Luke Luo, Ruth |
| author_facet | Hawranick, Luke Luo, Ruth |
| contents | An edge-coloring of a hypergraph is {\em spanning} if every vertex sees every color used in the coloring. In this paper, we prove that for $k \geq 2r \geq 6$, in any spanning $k$-coloring of the edges of a complete $r$-partite $r$-uniform hypergraph $H$, the vertices of $H$ can be covered by a set of at most $k-r+1$ monochromatic connected components. This proves a conjecture of Gyárfás and Király which is related to a special case of Ryser's conjecture. We also prove that for $k \in \{2,3\}$, every spanning $k$-edge-coloring of a complete bipartite graph admits a covering of its vertices using at most $k$ monochromatic components. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04704 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Covering complete $r$-partite hypergraphs with few monochromatic components Hawranick, Luke Luo, Ruth Combinatorics An edge-coloring of a hypergraph is {\em spanning} if every vertex sees every color used in the coloring. In this paper, we prove that for $k \geq 2r \geq 6$, in any spanning $k$-coloring of the edges of a complete $r$-partite $r$-uniform hypergraph $H$, the vertices of $H$ can be covered by a set of at most $k-r+1$ monochromatic connected components. This proves a conjecture of Gyárfás and Király which is related to a special case of Ryser's conjecture. We also prove that for $k \in \{2,3\}$, every spanning $k$-edge-coloring of a complete bipartite graph admits a covering of its vertices using at most $k$ monochromatic components. |
| title | Covering complete $r$-partite hypergraphs with few monochromatic components |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.04704 |