Proof of a tiling conjecture of Komlós

Authors:

Abstract
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, where χcr(H) denotes the critical chromatic number of H, 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. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003
Funding Information
  • National Science Foundation (IIS-0136337)
  • DIMACS (Center for Discrete Mathematics and Theoretical Computer Science)

This publication has 10 references indexed in Scilit: