2025/10/02 by Xu Liu, Bo Ning, Liu, Xu +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Mathematics and Applications #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2510.01880
openalex publication_date 2025/10/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 δc(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,kC3), 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.