K_r-factors in graphs with low independence number

DOI10.1016/J.JCTB.2020.12.006zbMATH Open1459.05329arXiv1912.00230OpenAlexW3115851297MaRDI QIDQ1998757FDOQ1998757

Pascal Su, Charlotte Knierim

Publication date: 8 March 2021

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

Abstract: A classical result by Hajnal and Szemer'edi from 1970 determines the minimal degree conditions necessary to guarantee for a graph to contain a $K_r$-factor. Namely, any graph on $n$ vertices, with minimum degree $delta(G)geleft(1-frac1right)n$ and $r$ dividing $n$ has a $K_r$-factor. This result is tight but the extremal examples are unique in that they all have a large independent set which is the bottleneck. Nenadov and Pehova showed that by requiring a sub-linear independence number the minimum degree condition in the Hajnal-Szemer'edi theorem can be improved. We show that, with the same minimum degree and sub-linear independence number, we can find a clique-factor with double the clique size. More formally, we show for every $rinmathbbN$ and constant $mu>0$ there is a positive constant $gamma$ such that every graph $G$ on $n$ vertices with $delta(G)geleft(1-frac2r+muight)n$ and $alpha(G)<gamman$ has a $K_r$-factor. We also give examples showing the minimum degree condition is asymptotically best possible.

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

Recommendations

• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• Embedding clique-factors in graphs with low \(\ell\)-independence number
• A note on independent sets in graphs with large minimum degree and small cliques
• Triangle factors of graphs without large independent sets and of weighted graphs
• A degree condition for the existence of regular factors inK1,n-free graphs

zbMATH Keywords

graph embedding[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Hajnal-Szemer%EF%BF%BD%EF%BF%BDdi+theorem&go=Go Hajnal-Szemer��di theorem][https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Ramsey-Tur%EF%BF%BD%EF%BF%BDn+theory&go=Go Ramsey-Tur��n theory]

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Ramsey theory (05D10)

Cites Work

• A degree sequence Hajnal-Szemerédi theorem
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• 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
• Some Theorems on Abstract Graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Ramsey-Turán theory
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• On a Ramsey-Turán type problem
• A few remarks on Ramsey--Turán-type problems
• Graph Theory and Probability. II
• Title not available (Why is that?)
• More results on Ramsey-Turán type problems
• Perfect matchings in uniform hypergraphs with large minimum degree
• Tripartite version of the Corrádi-Hajnal theorem
• Title not available (Why is that?)
• Quadripartite version of the Hajnal-Szemerédi theorem
• On a Ramsey--Turán Variant of the Hajnal--Szemerédi Theorem
• Title not available (Why is that?)
• Triangle factors of graphs without large independent sets and of weighted graphs
• Triangle-Tilings in Graphs Without Large Independent Sets

Cited In (8)

• Large \(Y_{3,2}\)-tilings in 3-uniform hypergraphs
• Clique-factors in graphs with sublinear -independence number
• Embedding clique-factors in graphs with low \(\ell\)-independence number
• A Ramsey–Turán theory for tilings in graphs
• \(H\)-factors in graphs with small independence number
• On powers of Hamilton cycles in Ramsey-Turán theory
• Spanning trees in graphs without large bipartite holes
• Disjoint cycles in graphs with restricted independence number

This page was built for publication: \(K_r\)-factors in graphs with low independence number

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