On the proper rainbow saturation numbers of cliques, paths, and odd cycles
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917803413471232 |
|---|---|
| author | Baker, Dustin Gomez-Leos, Enrique Halfpap, Anastasia Heath, Emily Martin, Ryan R. Miller, Joe Parker, Alex Pungello, Hope Schwieder, Coy Veldt, Nick |
| author_facet | Baker, Dustin Gomez-Leos, Enrique Halfpap, Anastasia Heath, Emily Martin, Ryan R. Miller, Joe Parker, Alex Pungello, Hope Schwieder, Coy Veldt, Nick |
| contents | Given a graph $H$, we say a graph $G$ is properly rainbow $H$-saturated if there is a proper edge-coloring of $G$ which contains no rainbow copy of $H$, but adding any edge to $G$ makes such an edge-coloring impossible. The proper rainbow saturation number, denoted $\text{sat}^*(n,H)$, is the minimum number of edges in an $n$-vertex rainbow $H$-saturated graph. We determine the proper rainbow saturation number for paths up to an additive constant and asymptotically determine $\text{sat}^*(n,K_4)$. In addition, we bound $\text{sat}^*(n,H)$ when $H$ is a larger clique, tree of diameter at least 4, or odd cycle. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15258 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the proper rainbow saturation numbers of cliques, paths, and odd cycles Baker, Dustin Gomez-Leos, Enrique Halfpap, Anastasia Heath, Emily Martin, Ryan R. Miller, Joe Parker, Alex Pungello, Hope Schwieder, Coy Veldt, Nick Combinatorics Given a graph $H$, we say a graph $G$ is properly rainbow $H$-saturated if there is a proper edge-coloring of $G$ which contains no rainbow copy of $H$, but adding any edge to $G$ makes such an edge-coloring impossible. The proper rainbow saturation number, denoted $\text{sat}^*(n,H)$, is the minimum number of edges in an $n$-vertex rainbow $H$-saturated graph. We determine the proper rainbow saturation number for paths up to an additive constant and asymptotically determine $\text{sat}^*(n,K_4)$. In addition, we bound $\text{sat}^*(n,H)$ when $H$ is a larger clique, tree of diameter at least 4, or odd cycle. |
| title | On the proper rainbow saturation numbers of cliques, paths, and odd cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.15258 |