Monochromatic triangle-tilings in dense graphs without large independent sets

Abstract

Given two graphs $H$ and $G$, an $H$-tiling is a family of vertex-disjoint copies of $H$ in $G$. A perfect $H$-tiling covers all vertices of $G$. The Corradi-Hajnal theorem (1963) states that an $n$-vertex graph $G$ with minimum degree $\hat{I}´(G)\ge 2n/3$ contains a perfect triangle-tiling. For an $n$-vertex graph $G$ with independence number $\hat{I}\pm (G)=o(n)$, Balogh, Molla and Sharifzadeh (Random Structures & Algorithms, 2016) showed that a minimum degree of $(\frac{1}{2}+o(1))n$ forces a perfect triangle-tiling. In a 2-edge-colored graph, Balogh, Freschi, Treglown (European J. Combin. 2026) determined the (asymptotic) minimum degree threshold for forcing a strong or weak monochromatic triangle-tiling covering a prescribed proportion of the vertices: a strong tiling requires all triangles to be in the same color class, while a weak tiling only requires each triangle to be monochromatic. In this paper, we combine the conditions from these two lines of work and prove that every $2$-edge-colored $n$-vertex graph $G$ with $\hat{I}\pm (G)=o(n)$ contains a weak monochromatic triangle-tiling $\hat{I}“$ of size \[ |Γ|\ge \begin{cases} 2δ(G)-n-o(n), & \text{if }\frac12 n\le δ(G)\le \frac35 n,\\[2mm] δ(G)/3-o(n), & \text{if }δ(G)>\frac35 n. \end{cases} \] Both bounds are asymptotically optimal. We use the degree form regularity lemma in our proof.

21 pages, 1 figure