Approximate multipartite version of the Hajnal-Szemerédi theorem

DOI10.1016/J.JCTB.2011.10.003zbMATH Open1239.05100arXiv0807.4463OpenAlexW2040000805MaRDI QIDQ412166FDOQ412166

Marcelo Mydlarz, Béla Csaba

Publication date: 4 May 2012

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

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.

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)

Cites Work

• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the maximal number of independent circuits in a graph
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Blow-up lemma
• A fast algorithm for equitable coloring
• An algorithmic version of the blow-up lemma
• Title not available (Why is that?)
• Regular spanning subgraphs of bipartite graphs of high minimum degree
• Tripartite version of the Corrádi-Hajnal theorem
• Triangle-factors in a balanced blown-up triangle
• Title not available (Why is that?)
• Title not available (Why is that?)
• Variants of the Hajnal-Szemer�di Theorem
• Quadripartite version of the Hajnal-Szemerédi theorem

Cited In (8)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Cyclic triangle factors in regular tournaments
• A geometric theory for hypergraph matching
• Tiling tripartite graphs with 3-colorable graphs: the extreme case
• A multipartite Hajnal-Szemerédi theorem
• Embedding Graphs Having Ore-Degree at Most Five
• Triangle-Tilings in Graphs Without Large Independent Sets
• Asymptotic multipartite version of the Alon-Yuster theorem

   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 👍 👎
• Title not available (Why is that?) 👍 👎

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)