This paper confirms the Hu-Li-Yang conjecture for vertex-disjoint triangles, suggesting implications for anti-Ramsey numbers.
In 1963, Dirac proved that every n-vertex graph has k vertex-disjoint triangles if n≥ 3k and minimum degree δ(G)≥ n+k/2. The base case $n=3k$ can be reduced to the Corrádi-Hajnál Theorem. Towards a rainbow version of Dirac's Theorem, Hu, Li, and Yang conjectured that for all positive integers n and k with n≥ 3k, every edge-colored graph G of order n with δᶜ(G)≥ n+k/2 contains k vertex-disjoint rainbow triangles. In another direction, Wu et al. conjectured an exact formula for anti-Ramsey number ar(n,kC₃), generalizing the earlier work of Erdős, Sós and Simonovits. The conjecture of Hu, Li, and Yang was confirmed for the cases $k=1$ and $k=2$. However, Lo and Williams disproved the conjecture when n≤ 17k/5. It is therefore natural to ask whether the conjecture holds for $n=Ω(k)$. In this paper, we confirm this by showing that the Hu-Li-Yang conjecture holds when n≥ 42.5k+48. We disprove the conjecture of Wu et al. and propose a modified conjecture. This conjecture is motivated by previous works due to Allen, Böttcher, Hladký, and Piguet on Turán number of vertex-disjoint triangles.
No takes yet. Share an insight, caveat, or question.
Liu et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: