The rainbow saturation number is linear
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929314379857920 |
|---|---|
| author | Behague, Natalie Johnston, Tom Letzter, Shoham Morrison, Natasha Ogden, Shannon |
| author_facet | Behague, Natalie Johnston, Tom Letzter, Shoham Morrison, Natasha Ogden, Shannon |
| contents | Given a graph $H$, we say that an edge-coloured graph $G$ is $H$-rainbow saturated if it does not contain a rainbow copy of $H$, but the addition of any non-edge in any colour creates a rainbow copy of $H$. The rainbow saturation number $\text{rsat}(n,H)$ is the minimum number of edges among all $H$-rainbow saturated edge-coloured graphs on $n$ vertices. We prove that for any non-empty graph $H$, the rainbow saturation number is linear in $n$, thus proving a conjecture of Girão, Lewis, and Popielarz. In addition, we also give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Girão, Lewis, and Popielarz. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_08589 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The rainbow saturation number is linear Behague, Natalie Johnston, Tom Letzter, Shoham Morrison, Natasha Ogden, Shannon Combinatorics Given a graph $H$, we say that an edge-coloured graph $G$ is $H$-rainbow saturated if it does not contain a rainbow copy of $H$, but the addition of any non-edge in any colour creates a rainbow copy of $H$. The rainbow saturation number $\text{rsat}(n,H)$ is the minimum number of edges among all $H$-rainbow saturated edge-coloured graphs on $n$ vertices. We prove that for any non-empty graph $H$, the rainbow saturation number is linear in $n$, thus proving a conjecture of Girão, Lewis, and Popielarz. In addition, we also give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Girão, Lewis, and Popielarz. |
| title | The rainbow saturation number is linear |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2211.08589 |