Clique-factors in graphs with low K_ℓ-independence number

2025/09/21 by Ming Chen, Jie Han, Chen, Ming +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2509.16851

openalex publication_date 2025/09/21 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28

Abstract

Given r∈ ℕ with r≥ 4, we show that there exists n₀∈ ℕ such that for every n≥ n₀, every n-vertex graph G with δ(G)≥ ((1)/(2)+o(1))n and α_r-2(G)=o(n) contains a K_r-factor. This resolves the first open case of a question proposed by Nenadov and Pehova, and reiterated by Knierm and Su. We further introduce two lower bound constructions that, along with some known results, fully resolve a question presented by Balogh, Molla, and Sharifzadeh.

Citations

• H-factors in graphs with small independence number
• A Ramsey-Turán theory for tilings in graphs
• K_r-Factors in Graphs with Low Independence Number
• Triangle-tilings in graphs without large independent sets
• Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs
• On directed versions of the Hajnal--Szemerédi theorem
• Embedding large subgraphs into dense graphs
• The minimum degree threshold for perfect graph packings
• On the Complexity of General Graph Factor Problems
• Some Theorems on Abstract Graphs

Related

• Embedding clique-factors in graphs with low ℓ-independence number
• Clique-factors in graphs with sublinear ℓ-independence number
• K_r-Factors in Graphs with Low Independence Number
• H-factors in graphs with small independence number
• Clique-factors in sparse pseudorandom graphs