Proof of a tiling conjecture of Komlós

DOI10.1002/rsa.10091zbMath1029.05121OpenAlexW2138464776WikidataQ123237753 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 lemmatilingcritical chromatic numberblow-up lemma

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (22)

An Asymptotic Multipartite Kühn--Osthus Theorem ⋮ Minimum degree thresholds for bipartite graph tiling ⋮ Dirac-type results for tilings and coverings in ordered graphs ⋮ The minimum degree threshold for perfect graph packings ⋮ Minimum \(H\)-decompositions of graphs ⋮ Disjoint cycles and chorded cycles in a graph with given minimum degree ⋮ Embedding clique-factors in graphs with low \(\ell\)-independence number ⋮ Graph Tilings in Incompatibility Systems ⋮ Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu ⋮ A degree sequence version of the Kühn-Osthus tiling theorem ⋮ A Ramsey–Turán theory for tilings in graphs ⋮ On multipartite Hajnal-Szemerédi theorems ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ The Complexity of Perfect Packings in Dense 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 ⋮ The complexity of perfect matchings and packings in dense hypergraphs ⋮ On Komlós’ tiling theorem in random graphs ⋮ Bandwidth theorem for random graphs ⋮ A Degree Sequence Komlós Theorem ⋮ On the decomposition threshold of a given graph

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

This page was built for publication: Proof of a tiling conjecture of Komlós