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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• On the maximal number of independent circuits in a graph
• Blow-up lemma
• A fast algorithm for equitable coloring
• An algorithmic version of the blow-up lemma
• 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
• 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

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On the degree conjecture for separability of multipartite quantum states 👍 👎
• Multipartite generalization of the Schmidt decomposition 👍 👎
• On multipartite Hajnal-Szemerédi theorems 👍 👎
• A multipartite Hajnal-Szemerédi theorem 👍 👎
• Asymptotic multipartite version of the Alon-Yuster theorem 👍 👎
• A strengthening and a multipartite generalization of the Alon-Boppana-Serre theorem 👍 👎
• A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs 👍 👎
• A note on the degree conjecture for separability of multipartite quantum states 👍 👎

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)