K_r-factors in graphs with low independence number

DOI10.1016/J.JCTB.2020.12.006MaRDI QIDQ1998757zbMATH OpenOpenAlexFDO

Authors Charlotte Knierim, Pascal Su

Publication date 8 March 2021

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

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

zbMATH Keywords

graph embeddingHajnal-Szemerédi theoremRamsey-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)

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.

Recommendations

• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• Embedding clique-factors in graphs with low -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

Cites work

• scientific article; zbMATH DE number 3765840 (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 6302978 (Why is no real title available?)
• scientific article; zbMATH DE number 3333194 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• A degree sequence Hajnal-Szemerédi theorem
• A few remarks on Ramsey--Turán-type problems
• An approximate Dirac-type theorem for k-uniform hypergraphs
• Graph Theory and Probability. II
• More results on Ramsey-Turán type problems
• On a Ramsey-Turán type problem
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• On the maximal number of independent circuits in a graph
• Perfect matchings in uniform hypergraphs with large minimum degree
• Quadripartite version of the Hajnal-Szemerédi theorem
• Ramsey-Turán theory
• Some Theorems on Abstract Graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Triangle factors of graphs without large independent sets and of weighted graphs
• Triangle-tilings in graphs without large independent sets
• Tripartite version of the Corrádi-Hajnal theorem

Cited in

(12)

• A note on independent sets in graphs with large minimum degree and small cliques
• Large \(Y_{3,2}\)-tilings in 3-uniform hypergraphs
• Generalized Ramsey-Turán density for cliques
• Clique-factors in graphs with sublinear -independence number
• Triangle factors of graphs without large independent sets and of weighted graphs
• Embedding clique-factors in graphs with low -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
• On a Ramsey-Turán variant of the Hajnal-Szemerédi theorem
• 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)