The absence of monochromatic triangle implies various properly colored spanning trees
| Autor: | Li, Ruonan, Lu, Ruhui, Su, Xueli, Zhang, Shenggui |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 15 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|