The asymptotic minimum-degree characterization for H-factors with acyclic-partition hcf 1
The asymptotic minimum-degree characterization for H-factors with acyclic-partition hcf 1
Let be a graph, let denote the family of all acyclic partitions of with parts, and let be the associated gcd parameter. For a graph , define its critical arboricity by
where is the minimum size of a part over all optimal acyclic partitions of .
The asymptotic -factor conjecture. Given , , and an -vertex graph with , there exists such that, for all sufficiently large , every -vertex graph satisfying
and contains an -factor.
The conjecture proposes the missing converse to the paper's asymptotic sharpness results for the minimum-degree condition in the -factor problem. The lower bound from the space barrier establishes sharpness for graphs with critical arboricity attaining the relevant threshold, while the case is already covered by the stated dichotomy; the general case remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ming Chen, Jie Han, Guanghui Wang and Donglei Yang, “H-factors in graphs with small independence number”, arXiv:2207.03058 (2022).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.