Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2504.00288 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913769268969472 |
|---|---|
| author | Berikkyzy, Zhanar Miller, Joe Warnberg, Nathan |
| author_facet | Berikkyzy, Zhanar Miller, Joe Warnberg, Nathan |
| contents | The anti-van der Waerden number of a graph $G$ is the fewest number of colors needed to guarantee a rainbow $3$-term arithmetic progression in $G$, denoted $\operatorname{aw}(G,3)$. It is known that the anti-van der Waerden number of graph products is $3 \le \operatorname{aw}(G\square H,3)\le 4$. Previous work has been done on classifying families of graph products into $\operatorname{aw}(G\square H,3) = 3$ and $\operatorname{aw}(G\square H,3) = 4$. Some of these families include the product of two paths, the product of paths and cycles, the product of two cycles, and the product of odd cycles with any graph. Recently, a partial characterization of the product of two trees was established. This paper completes the characterization for $\operatorname{aw}(T\square T',3)$ where $T$ and $T'$ are trees. Moreover, this result extends to a full classification of products of forests. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_00288 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Full classification of anti-van der Waerden numbers of graph products of forests Berikkyzy, Zhanar Miller, Joe Warnberg, Nathan Combinatorics 05C05, 05C12, 05C15, 05C35, 05C76 The anti-van der Waerden number of a graph $G$ is the fewest number of colors needed to guarantee a rainbow $3$-term arithmetic progression in $G$, denoted $\operatorname{aw}(G,3)$. It is known that the anti-van der Waerden number of graph products is $3 \le \operatorname{aw}(G\square H,3)\le 4$. Previous work has been done on classifying families of graph products into $\operatorname{aw}(G\square H,3) = 3$ and $\operatorname{aw}(G\square H,3) = 4$. Some of these families include the product of two paths, the product of paths and cycles, the product of two cycles, and the product of odd cycles with any graph. Recently, a partial characterization of the product of two trees was established. This paper completes the characterization for $\operatorname{aw}(T\square T',3)$ where $T$ and $T'$ are trees. Moreover, this result extends to a full classification of products of forests. |
| title | Full classification of anti-van der Waerden numbers of graph products of forests |
| topic | Combinatorics 05C05, 05C12, 05C15, 05C35, 05C76 |
| url | https://arxiv.org/abs/2504.00288 |