Asymptotic multipartite version of the Alon-Yuster theorem

DOI10.1016/J.JCTB.2017.05.004MaRDI QIDQ2407378zbMATH OpenOpenAlexFDO

Authors Ryan R. Martin, J. Skokan

Publication date 29 September 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Alon-YusterHajnal-Szemerédi theoremlinear programmingmultipartite theoremregularitytiling

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Linear programming (90C05)

Abstract: In this paper, we prove the asymptotic multipartite version of the Alon-Yuster theorem, which is a generalization of the Hajnal-Szemer'edi theorem: If $kgeq3$ is an integer, $H$ is a $k$-colorable graph and $gamma>0$ is fixed, then, for every sufficiently large $n$, where $|V(H)|$ divides $n$, and for every balanced $k$-partite graph $G$ on $kn$ vertices with each of its corresponding $$ bipartite subgraphs having minimum degree at least $(k-1)n/k+gamman$, $G$ has a subgraph consisting of $kn/|V(H)|$ vertex-disjoint copies of $H$. The proof uses the Regularity method together with linear programming.

Recommendations

• An asymptotic multipartite Kühn-Osthus theorem
• On multipartite Hajnal-Szemerédi theorems
• Approximate multipartite version of the Hajnal-Szemerédi theorem
• A common extension of the Erdős-Stone theorem and the Alon-Yuster theorem for unbounded graphs
• Proof of the Alon-Yuster conjecture

Cites work

• \(H\)-factors in dense graphs
• A fast algorithm for equitable coloring
• A geometric theory for hypergraph matching
• A multipartite Hajnal-Szemerédi theorem
• A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
• A note on bipartite graph tiling
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Approximate multipartite version of the Hajnal-Szemerédi theorem
• Bipartite graph tiling
• Blow-up lemma
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3693321 (Why is no real title available?)
• scientific article; zbMATH DE number 3497901 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Minimum degree thresholds for bipartite graph tiling
• Note on bipartite graph tilings
• On Representatives of Subsets
• On the maximal number of independent circuits in a graph
• Proof of the Alon-Yuster conjecture
• Quadripartite version of the Hajnal-Szemerédi theorem
• The minimum degree threshold for perfect graph packings
• Tiling tripartite graphs with 3-colorable graphs
• Tiling Turán theorems
• Triangle-factors in a balanced blown-up triangle
• 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
• Powers of Hamiltonian cycles in multipartite graphs
• Triangle-tilings in graphs without large independent sets
• Approximate multipartite version of the Hajnal-Szemerédi theorem
• An asymptotic multipartite Kühn-Osthus theorem
• Proof of the Alon-Yuster conjecture
• Sufficient conditions for perfect mixed tilings
• A common extension of the Erdős-Stone theorem and the Alon-Yuster theorem for unbounded graphs

This page was built for publication: Asymptotic multipartite version of the Alon-Yuster theorem

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