Proper Rainbow Saturation Numbers for Cycles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911454591975424 |
|---|---|
| author | Halfpap, Anastasia Lidický, Bernard Masařík, Tomáš |
| author_facet | Halfpap, Anastasia Lidický, Bernard Masařík, Tomáš |
| contents | We say that an edge-coloring of a graph $G$ is proper if every pair of incident edges receive distinct colors, and is rainbow if no two edges of $G$ receive the same color. Furthermore, given a fixed graph $F$, we say that $G$ is rainbow $F$-saturated if $G$ admits a proper edge-coloring which does not contain any rainbow subgraph isomorphic to $F$, but the addition of any edge to $G$ makes such an edge-coloring impossible. The maximum number of edges in a rainbow $F$-saturated graph is the rainbow Turán number, whose study was initiated in 2007 by Keevash, Mubayi, Sudakov, and Verstraëte. Recently, Bushaw, Johnston, and Rombach introduced study of a corresponding saturation problem, asking for the minimum number of edges in a rainbow $F$-saturated graph. We term this minimum the proper rainbow saturation number of $F$, denoted $\mathrm{sat}^*(n,F)$. We asymptotically determine $\mathrm{sat}^*(n,C_4)$, answering a question of Bushaw, Johnston, and Rombach. We also exhibit constructions which establish upper bounds for $\mathrm{sat}^*(n,C_5)$ and $\mathrm{sat}^*(n,C_6)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_15602 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Proper Rainbow Saturation Numbers for Cycles Halfpap, Anastasia Lidický, Bernard Masařík, Tomáš Combinatorics Discrete Mathematics We say that an edge-coloring of a graph $G$ is proper if every pair of incident edges receive distinct colors, and is rainbow if no two edges of $G$ receive the same color. Furthermore, given a fixed graph $F$, we say that $G$ is rainbow $F$-saturated if $G$ admits a proper edge-coloring which does not contain any rainbow subgraph isomorphic to $F$, but the addition of any edge to $G$ makes such an edge-coloring impossible. The maximum number of edges in a rainbow $F$-saturated graph is the rainbow Turán number, whose study was initiated in 2007 by Keevash, Mubayi, Sudakov, and Verstraëte. Recently, Bushaw, Johnston, and Rombach introduced study of a corresponding saturation problem, asking for the minimum number of edges in a rainbow $F$-saturated graph. We term this minimum the proper rainbow saturation number of $F$, denoted $\mathrm{sat}^*(n,F)$. We asymptotically determine $\mathrm{sat}^*(n,C_4)$, answering a question of Bushaw, Johnston, and Rombach. We also exhibit constructions which establish upper bounds for $\mathrm{sat}^*(n,C_5)$ and $\mathrm{sat}^*(n,C_6)$. |
| title | Proper Rainbow Saturation Numbers for Cycles |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2403.15602 |