Linear lower-bound conjecture for factors of non-central graphs

Let $H$ be a fixed graph, let $\operatorname{\mathcal{P}}_H$ be the family of graphs on $n$ vertices containing an $H$-factor, and let $\tau(\sigma,\operatorname{\mathcal{P}}_H)$ be the first round in which Builder's graph belongs to this family. A graph $H$ is central if it has a vertex $v$ such that deleting any edge incident to $v$ disconnects $H$; otherwise, $H$ is non-central. The notation $f(n)\gg n$ means that $f(n)/n\to\infty$.

Non-central-factor conjecture. Let $H$ be a fixed non-central graph. Then, for every strategy $\sigma\in\operatorname{\mathcal{S}}_n$,

$$\tau(\sigma,\operatorname{\mathcal{P}}_H)\gg n$$

whp.

The theorem preceding the conjecture gives linear-time constructions for central graphs, whereas the conjecture predicts a superlinear lower bound for every strategy when $H$ is non-central. The paper notes that cycles and complete graphs are natural cases not covered by the theorem, and that the conjectured scale lies between the linear constructions and the naive $O(n\log n)$ strategy.