Large rainbow matchings in edge-colored graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916053906358272 |
|---|---|
| author | Chakraborti, Debsoumya Loh, Po-Shen |
| author_facet | Chakraborti, Debsoumya Loh, Po-Shen |
| contents | A subgraph of an edge-colored graph is called \emph{rainbow} if all of its edges have distinct colors. There has been much research on the topic of finding a large rainbow matching in a properly edge-colored graph, where a proper edge-coloring is a coloring of the edge set such that no same-colored edges are incident. Gao, Ramadurai, Wanless, and Wormald proved that in every proper edge-coloring of a graph with $n$ colors where each color appears at least $n+o(n)$ times, there is always a rainbow matching using every color. We strengthen this result by simultaneously relaxing three conditions: (i) we lift the condition on the number of colors and allow any finite number of colors and instead, put a weaker condition requiring the maximum degree of the graph to be at most $n$, (ii) we relax the proper coloring condition and require that the graph induced by each of the colors have maximum degree $o(n)$, and (iii) we work in a more general setting of multigraphs allowing edge multiplicities to be $o(n)$.
As an application of this result, we show that for every proper edge-coloring of a graph with $2n+o(n)$ colors where each color appears at least $n$ times, there is always a rainbow matching of size $n$. Aharoni and Berger conjectured that $2n+o(n)$ can be replaced by $n+1$ in this statement. We dispute this conjecture with an explicit construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_04650 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Large rainbow matchings in edge-colored graphs Chakraborti, Debsoumya Loh, Po-Shen Combinatorics A subgraph of an edge-colored graph is called \emph{rainbow} if all of its edges have distinct colors. There has been much research on the topic of finding a large rainbow matching in a properly edge-colored graph, where a proper edge-coloring is a coloring of the edge set such that no same-colored edges are incident. Gao, Ramadurai, Wanless, and Wormald proved that in every proper edge-coloring of a graph with $n$ colors where each color appears at least $n+o(n)$ times, there is always a rainbow matching using every color. We strengthen this result by simultaneously relaxing three conditions: (i) we lift the condition on the number of colors and allow any finite number of colors and instead, put a weaker condition requiring the maximum degree of the graph to be at most $n$, (ii) we relax the proper coloring condition and require that the graph induced by each of the colors have maximum degree $o(n)$, and (iii) we work in a more general setting of multigraphs allowing edge multiplicities to be $o(n)$. As an application of this result, we show that for every proper edge-coloring of a graph with $2n+o(n)$ colors where each color appears at least $n$ times, there is always a rainbow matching of size $n$. Aharoni and Berger conjectured that $2n+o(n)$ can be replaced by $n+1$ in this statement. We dispute this conjecture with an explicit construction. |
| title | Large rainbow matchings in edge-colored graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2011.04650 |