Minimum degree thresholds for bipartite graph tiling

DOI10.1002/JGT.20605MaRDI QIDQ2888882zbMATH OpenOpenAlexFDO

Authors Albert Bush, Yi Zhao

Publication date 4 June 2012

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4585

zbMATH Keywords

blow-up lemmacritical chromatic numbergraph packingregularity lemmatiling

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For any bipartite graph $H$, we determine a minimum degree threshold for a balanced bipartite graph $G$ to contain a perfect $H$-tiling. We show that this threshold is best possible up to a constant depending only on $H$. Additionally, we prove a corresponding minimum degree threshold to guarantee that $G$ has an $H$-tiling missing only a constant number of vertices. Our threshold for the perfect tiling depends on either the chromatic number $chi(H)$ or the critical chromatic number $ch{i}_{cr}(H)$ while the threshold for the almost perfect tiling only depends on $ch{i}_{cr}(H)$. Our results answer two questions of Zhao. They can be viewed as bipartite analogs to the results of Kuhn and Osthus and of Shokoufandeh and Zhao.

Recommendations

• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• Bipartite graph tiling
• A note on bipartite graph tiling
• Note on bipartite graph tilings
• Minimum \(k\)-critical bipartite graphs
• The decomposition threshold for bipartite graphs with minimum degree one
• On degree sets and the minimum orders in bipartite graphs
• Codegree threshold for tiling \(k\)-graphs with two edges sharing exactly \(\ell\) vertices
• Graph partitions with minimum degree constraints

Cites work

• \(H\)-factors in dense graphs
• Bipartite graph tiling
• Blow-up lemma
• Note on bipartite graph tilings
• On Representatives of Subsets
• Problems and results on judicious partitions
• Proof of a tiling conjecture of Komlós
• Proof of the Alon-Yuster conjecture
• Quadripartite version of the Hajnal-Szemerédi theorem
• Some Theorems on Abstract Graphs
• Tiling tripartite graphs with 3-colorable graphs
• Tiling Turán theorems
• Tripartite version of the Corrádi-Hajnal theorem
• Variants of the Hajnal-Szemer�di Theorem

Cited in

(10)

• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Tiling tripartite graphs with 3-colorable graphs: the extreme case
• On multipartite Hajnal-Szemerédi theorems
• Asymptotic multipartite version of the Alon-Yuster theorem
• A note on bipartite graph tiling
• Bipartite graph tiling
• A discrepancy version of the Hajnal-Szemerédi theorem
• Dirac-type results for tilings and coverings in ordered graphs
• An asymptotic multipartite Kühn-Osthus theorem
• Note on bipartite graph tilings

This page was built for publication: Minimum degree thresholds for bipartite graph tiling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2888882)