DIMACS TR: 2001-36
On a Tiling Conjecture of Komlos for 3-Chromatic Graphs
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$, 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