Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.01302 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929655626334208 |
|---|---|
| author | Goddard, Wayne Herrman, Tyler Hughes, Simon J. |
| author_facet | Goddard, Wayne Herrman, Tyler Hughes, Simon J. |
| contents | For a graph with colored vertices, a rainbow subgraph is one where all vertices have different colors. For graph $G$, let $c_k(G)$ denote the maximum number of different colors in a coloring without a rainbow path on $k$ vertices, and $cp_k(G)$ the maximum number of colors if the coloring is required to be proper. The parameter $c_3$ has been studied by multiple authors. We investigate these parameters for trees and $k \ge 4$. We first calculate them when $G$ is a path, and determine when the optimal coloring is unique. Then for trees $T$ of order $n$, we show that the minimum value of $c_4(T)$ and $cp_4(T)$ is $(n+2)/2$, and the trees with the minimum value of $cp_4(T)$ are the coronas. Further, the minimum value of $c_5(T)$ and $cp_5(T)$ is $(n+3)/2$ , and the trees with the minimum value of either parameter are octopuses. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01302 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounds on Coloring Trees without Rainbow Paths Goddard, Wayne Herrman, Tyler Hughes, Simon J. Combinatorics 05C15 For a graph with colored vertices, a rainbow subgraph is one where all vertices have different colors. For graph $G$, let $c_k(G)$ denote the maximum number of different colors in a coloring without a rainbow path on $k$ vertices, and $cp_k(G)$ the maximum number of colors if the coloring is required to be proper. The parameter $c_3$ has been studied by multiple authors. We investigate these parameters for trees and $k \ge 4$. We first calculate them when $G$ is a path, and determine when the optimal coloring is unique. Then for trees $T$ of order $n$, we show that the minimum value of $c_4(T)$ and $cp_4(T)$ is $(n+2)/2$, and the trees with the minimum value of $cp_4(T)$ are the coronas. Further, the minimum value of $c_5(T)$ and $cp_5(T)$ is $(n+3)/2$ , and the trees with the minimum value of either parameter are octopuses. |
| title | Bounds on Coloring Trees without Rainbow Paths |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2501.01302 |