Approximate multipartite version of the Hajnal-Szemerédi theorem

DOI10.1016/J.JCTB.2011.10.003MaRDI QIDQ412166zbMATH OpenOpenAlexFDO

Authors Béla Csaba, Marcelo Mydlarz

Publication date 4 May 2012

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

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

zbMATH Keywords

regularity lemmamultipartite form of the Hajnal-Szemerédi theorem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $q$ be a positve integer, and $G$ be a $q$-partite simple graph on $qn$ vertices, with $n$ vertices in each vertex class. Let $delta=k_{q}over{k}_q+1$, where $k_q=q+O(logq)$. If each vertex of $G$ is adjacent to at least $deltan$ vertices in each of the other vertex classes, $q$ is bounded and $n$ is large enough, then $G$ has a $K_q$-factor.

Recommendations

• A multipartite Hajnal-Szemerédi theorem
• A multipartite Hajnal-Szemerédi theorem
• On multipartite Hajnal-Szemerédi theorems
• Asymptotic multipartite version of the Alon-Yuster theorem
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem
• Multipartite generalization of the Schmidt decomposition
• A note on the degree conjecture for separability of multipartite quantum states
• On the degree conjecture for separability of multipartite quantum states
• A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
• scientific article

Cites work

• scientific article; zbMATH DE number 3693321 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1944144 (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?)
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• A fast algorithm for equitable coloring
• An algorithmic version of the blow-up lemma
• Blow-up lemma
• Factors of \(r\)-partite graphs and bounds for the strong chromatic number.
• On the maximal number of independent circuits in a graph
• Quadripartite version of the Hajnal-Szemerédi theorem
• Regular spanning subgraphs of bipartite graphs of high minimum degree
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• 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)

• Triangle-tilings in graphs without large independent sets
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Embedding graphs having Ore-degree at most five
• Cyclic triangle factors in regular tournaments
• A geometric theory for hypergraph matching
• Tiling tripartite graphs with 3-colorable graphs: the extreme case
• On multipartite Hajnal-Szemerédi theorems
• A multipartite Hajnal-Szemerédi theorem
• Asymptotic multipartite version of the Alon-Yuster theorem
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem

This page was built for publication: Approximate multipartite version of the Hajnal-Szemerédi theorem

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