The absence of monochromatic triangle implies various properly colored spanning trees

Ruonan Li; Ruhui Lu; Xueli Su; Shenggui Zhang

doi:10.1016/j.disc.2026.115131

paper

The absence of monochromatic triangle implies various properly colored spanning trees

arXiv:2403.09082 · doi:10.1016/j.disc.2026.115131

Abstract

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 $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 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.

15 pages