Proof of a tiling conjecture of Komlós
Authors:
- 9 May 2003
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 23 (2) , 180-205
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, 2003Keywords
Funding Information
- National Science Foundation (IIS-0136337)
- DIMACS (Center for Discrete Mathematics and Theoretical Computer Science)
This publication has 10 references indexed in Scilit:
- Proof of the Alon–Yuster conjectureDiscrete Mathematics, 2001
- Tiling Turán TheoremsCombinatorica, 2000
- An algorithmic version of the blow-up lemmaRandom Structures & Algorithms, 1998
- On sphere ordersDiscrete Mathematics, 1998
- Blow-up LemmaCombinatorica, 1997
- H-Factors in Dense GraphsJournal of Combinatorial Theory, Series B, 1996
- AlmostH-factors in dense graphsGraphs and Combinatorics, 1992
- On circuits in graphsDiscrete Mathematics, 1984
- On the maximal number of independent circuits in a graphActa Mathematica Hungarica, 1963
- Some Theorems on Abstract GraphsProceedings of the London Mathematical Society, 1952