DIMACS TR: 2001-36

On a Tiling Conjecture of Komlos for 3-Chromatic Graphs

Authors: Ali Shokoufandeh and Yi Zhao


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$, when $H$ is a 3-chromatic graph.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-35.ps.gz
DIMACS Home Page