Let $\Cvec$ be a fixed orientation of the cycle $C_\ell$, $\ell\ge3$, which is not directed. For an oriented graph $D$, let $d_D^*(v):=\max\{d_D^+(v),d_D^-(v)\},$ and let \[ \sigore(D):=\min\bigl\{d_D^*(x)+d_D^*(y):x\ne y,\ xy,yx\notin A(D)\bigr\}, \] with $\sigore(D)=\infty$ if the underlying graph of $D$ is complete. We prove that, for every $\mu>0$, there exist $\gamma>0$ and $n_0$ such that every $n\ge n_0$ with $\ell\mid n$ and every $n$-vertex oriented graph $D$ satisfying \[ \alpha(D)\le\gamma n \text{ and } {\sigore(D)\ge\left(\frac34+\mu\right)n} \] contains a $\Cvec$-factor. {Additionally, for every fixed $s\ge2$ and every fixed real constant $C$, we construct arbitrarily large oriented graphs with $\sigore(D)\ge \frac34n+C$ that contain no $C_{2s}^{\ad}$-factor. More precisely, $C:=\frac34\alpha(D)-2$ for $s=2$ and $C:=\frac14\alpha(D)-\frac32$ for $s\ge3$.} This paper develops a weighted reduction framework adapted to dominant degree condition, proves the absorption lemma via closed-cluster merging with even-walk, and derives almost-perfect tiling structures by virtue of Farkas-lemma-based fractional decomposition.
Let $\overrightarrow{C}$ be any orientation of the cycle $C_{\ell}$ which is not directed. We prove that, for every integer $\ell\ge3$ and every $\mu>0$, there is a real $\gamma$ such that every sufficiently large oriented graph $D$ with $\ell\mid |D|$, minimum semidegree at least $(1/4+\mu)|D|$ and independence number at most $\gamma |D|$ has a $\overrightarrow{C}$-factor. The constant $1/4$ is asymptotically tight. This proof establishes Ramsey-Tur\'an type lattice absorption lemmas and an almost covering theorem via the oriented tree embedding lemma under chromatic number constraints.
Let $C_{2s}^{\mathrm{ad}}$ be the anti-directed cycle of length $2s$, where $s\geq2$. We prove that, for every $\mu>0$, every sufficiently large $n$-vertex oriented graph $D$ with $2s\mid n$, \[ \delta^0(D)\geq\left(\frac14+\mu\right)n \qquad\text{and}\qquad \alpha(D)=o(n) \] contains a $C_{2s}^{\mathrm{ad}}$-factor. The minimum semidegree threshold is asymptotically tight. The proof develops Ramsey--Tur\'an-type lattice-absorption lemmas with a transferral arising from the small-independence condition by virtue of a fork-type structure.
Jia Zhou, Yunshu Gao· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
