Proof of a tiling conjecture of Komlós

DOI10.1002/rsa.10091zbMath1029.05121WikidataQ123237753 ScholiaQ123237753MaRDI QIDQ4434471

Yi Zhao, Ali Shokoufandeh

Publication date: 10 November 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10091

zbMATH Keywords

regularity lemma; tiling; critical chromatic number; blow-up lemma

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C15: Coloring of graphs and hypergraphs

Related Items

Dirac-type results for tilings and coverings in ordered graphs, On Komlós’ tiling theorem in random graphs, A Degree Sequence Komlós Theorem, An Asymptotic Multipartite Kühn--Osthus Theorem, Combinatorial and computational aspects of graph packing and graph decomposition, Bandwidth theorem for random graphs, Spanning 3-colourable subgraphs of small bandwidth in dense graphs, Proof of the bandwidth conjecture of Bollobás and Komlós, Tiling tripartite graphs with 3-colorable graphs: the extreme case, On multipartite Hajnal-Szemerédi theorems, The minimum degree threshold for perfect graph packings, Disjoint cycles and chorded cycles in a graph with given minimum degree, A degree sequence version of the Kühn-Osthus tiling theorem, The complexity of perfect matchings and packings in dense hypergraphs, On the decomposition threshold of a given graph, Minimum \(H\)-decompositions of graphs, Minimum degree thresholds for bipartite graph tiling, The Complexity of Perfect Packings in Dense Graphs

Cites Work

• On circuits in graphs
• Almost \(H\)-factors in dense graphs
• Blow-up lemma
• Tiling Turán theorems
• \(H\)-factors in dense graphs
• An algorithmic version of the blow-up lemma
• On the maximal number of independent circuits in a graph
• Some Theorems on Abstract Graphs
• Proof of the Alon-Yuster conjecture