From finding a spanning subgraph H to an H-factor

2025/09/23 by Allan Lo, Lo, Allan · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2509.18832

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

Abstract

A typical Dirac-type problem in extremal graph theory is to determine the minimum degree threshold for a graph G to have a spanning subgraph H, e.g. the Dirac theorem. A natural following up problem would be to seek an H-factor, which a spanning set of vertex-disjoint copies of H. In this short note, we present a method of obtaining an upper bound on the minimum degree threshold for an H-factor from one for finding a spanning copy of H. As an application, we proved that, for all ε>0 and ℓ sufficiently large, any oriented graph G on ℓ m vertices with minimum semi-degree δ⁰(G) ≥ (3/8+ ε) k ℓ contains a C_ℓ-factor, where C_ℓ is an arbitrary orientation of a cycle on ℓ vertices. This improves a result of Wang, Yan and Zhang.

Citations

• Arbitrary orientations of Hamilton cycles in directed graphs of large minimum degree
• Arbitrary orientations of cycles in oriented graphs
• Powers of Hamilton cycles in oriented and directed graphs
• Cycle-factors in oriented graphs
• Cyclic triangle factors in regular tournaments
• Recent advances on Dirac-type problems for hypergraphs
• A survey on Hamilton cycles in directed graphs
• Arbitrary Orientations Of Hamilton Cycles In Oriented Graphs
• Embedding large subgraphs into dense graphs
• Triangle packings and 1-factors in oriented graphs
• A Dirac type result on Hamilton cycles in oriented graphs
• The minimum degree threshold for perfect graph packings
• Some Theorems on Abstract Graphs

Cited by

• The exact total degree threshold for the square of a Hamilton cycle in digraphs

Related

• Unbounded degree spanning hypertrees in Dirac hypergraphs
• Minimum Degree Threshold for H-factors with High Discrepancy
• Spanning subdivisions in Dirac graphs
• A Toolkit for Robust Thresholds
• Dirac's Condition for Spanning Halin Subgraphs