DIMACS TR: 2001-51
Proof of a Tiling Conjecture of Komlos
Authors: Ali Shokoufandeh and Yi Zhao
ABSTRACT
Given two graphs $G$ and $H$, an $H$-{\em matching} of $G$ (or a
{\em 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 {\em critical
chromatic number} of $H$ is the number $\chi_{cr}(H)=(r-1)h/(h-u)$.
A conjecture of Koml\'{o}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 $\left(1-(1/\chi_{cr}(H))\right)n$, then $G$
contains an $H$-matching that covers all but $K$ vertices of $G$.
In this paper we prove that the conjecture holds for all
sufficiently large values of $n$.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-51.ps.gz
DIMACS Home Page