The absence of monochromatic triangle implies various properly colored spanning trees
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_ | 1866910091663376384 |
|---|---|
| author | Li, Ruonan Lu, Ruhui Su, Xueli Zhang, Shenggui |
| author_facet | Li, Ruonan Lu, Ruhui Su, Xueli Zhang, Shenggui |
| contents | An edge-colored graph $G$ is called properly colored if every two adjacent edges are assigned different colors. A monochromatic triangle is a cycle of length 3 with all the edges having the same color. Given a tree $T_0$, let $\mathcal{T}(n,T_0)$ be the collection of $n$-vertex trees that are subdivisions of $T_0$. It is conjectured that for each fixed tree $T_0$, there is a function $f(T_0)$ such that for each integer $n\geq f(T_0)$ and each $T\in \mathcal{T}(n,T_0)$, every edge-colored complete graph $K_n$ without containing monochromatic triangle must contain a properly colored copy of $T$. We confirm the conjecture in the case that $T_0$ is a star. A weaker version of the above conjecture is also obtained. Moreover, to get a nice quantitative estimation of $f(T_0)$ when $T_0$ is a star requires determining the constraint Ramsey number of a monochromatic triangle and a rainbow star, which is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09082 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The absence of monochromatic triangle implies various properly colored spanning trees Li, Ruonan Lu, Ruhui Su, Xueli Zhang, Shenggui Combinatorics 05C05, 05C20 An edge-colored graph $G$ is called properly colored if every two adjacent edges are assigned different colors. A monochromatic triangle is a cycle of length 3 with all the edges having the same color. Given a tree $T_0$, let $\mathcal{T}(n,T_0)$ be the collection of $n$-vertex trees that are subdivisions of $T_0$. It is conjectured that for each fixed tree $T_0$, there is a function $f(T_0)$ such that for each integer $n\geq f(T_0)$ and each $T\in \mathcal{T}(n,T_0)$, every edge-colored complete graph $K_n$ without containing monochromatic triangle must contain a properly colored copy of $T$. We confirm the conjecture in the case that $T_0$ is a star. A weaker version of the above conjecture is also obtained. Moreover, to get a nice quantitative estimation of $f(T_0)$ when $T_0$ is a star requires determining the constraint Ramsey number of a monochromatic triangle and a rainbow star, which is of independent interest. |
| title | The absence of monochromatic triangle implies various properly colored spanning trees |
| topic | Combinatorics 05C05, 05C20 |
| url | https://arxiv.org/abs/2403.09082 |