On a tiling conjecture of Komlós for 3-chromatic graphs Original Research Article

Given two graphs G and H, an H-matching of G (or a tiling of G with H) is a subgraph of G consisting of vertex-disjoint copies of H. For an r-chromatic graph H on h vertices, we write u=u(H) for the smallest possible color-class size in any r-coloring of H. The critical chromatic number of H is the number χcr(H)=(r−1)h/(h−u). A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n-vertex graph of minimum degree at least (1−(1/χcr(H)))n, then G contains an H-matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n when H is a 3-chromatic graph.