On a tiling conjecture of Komlós for 3-chromatic graphs. (Q1426117): Difference between revisions

A tiling of a (\(rH\)-matching) of a graph \(G\) with respect to a graph \(H\) is a subgraph consisting of vertex-disjoint copies of \(H\). \(u= u(H)\) is the possible color-class size in any \(r\)-coloring of an \(r\)-chromatic graph \(H\) on \(h\) vertices. 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 sufficiently small degree then \(G\) contains an \(H\)-matching that covers all but at most \(K\) vertices of \(G\). The authors prove that the conjecture holds for all sufficiently large values of \(n\) when \(H\) is a 3-chromatic graph.