Skip to content
Preprint

Dominant-Degree Conditions for Ramsey--Tur\'an Factors of Non-Directed Cycle Orientations

Sep 2026 · 0 citations · 32 references
Mathematics

Abstract

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.

View source

Similar papers

Preprint Oct 2026

A near-linear Chv\'atal--Erd\H{o}s condition for Hamilton cycles in digraphs

For a digraph $D$, let $\alpha_2(D)$ be the largest size of a vertex set containing no directed $2$-cycle. Let $f_2(a)$ be the least positive integer $k$ such that every $k$-strongly connected digraph $D$ with $\alpha_2(D)\le a$ has a Hamilton cycle. Jackson and Ordaz conjectured that $f_2(a)\le a+1$. Towards this conj...

Cheng-Li Li, Bo Ning · 0 citations
Preprint Sep 2026

Unbalanced spectral Tur\'an problem for color-critical graphs with prescribed large maximum degree

Let $F$ be a connected color-critical graph with $\chi(F)=r+1\ge4$, let $S_{n,\Delta}^{(r)}=(n-\Delta)K_1\vee T(\Delta,r-1)$. We determine the graph of maximum adjacency spectral radius among all $n$-vertex $F$-free graphs with prescribed maximum degree $\Delta$. There is a constant $s_F\in[0,1)$ such that, for all suf...

Chang Liu · 1 citation
Preprint Oct 2026

Degree-square Tur\'an problem for two self-converse tournaments

For a fixed digraph $F$, let $\operatorname{ex}_2^+(n,F)$ be the maximum of $\sum_{v\in V(D)}d_D^+(v)^2$ over all $n$-vertex $F$-free digraphs. Ai et al. [arXiv:2606.03520, 2026] asked for which self-converse tournament $F$ one can determine $\operatorname{ex}_2^+(n,F)$. Let $TT_r$ denote a transitive tournament on $r$...

Zhuo-Ran Han, Yao-Jun Chen · 0 citations
Preprint Aug 2026

An entropy bridge from weighted to spectral Tur\'{a}n theorems

We establish an entropy bridge, and then use it to prove that for any color-critical graph $F$ with chromatic number $\chi(F)=r+1\ge 3$, there exists a constant $\lambda_0=\lambda_0(F)$ such that if $G$ is an $F$-free graph with $\lambda (G)\ge \lambda_0$, then for every $\ell\ge 1$ with $(r,\ell )\neq (2,2)$, \[ \lamb...

Yong-Tao Li · 0 citations
Preprint Aug 2026

Sharp Bisection Bounds for Digraphs

Fix an integer $d\ge1$. We prove that, for all sufficiently large $m$, every digraph $D$ with $m$ arcs and minimum semidegree at least $d$ admits a bisection $V(D)=V_1\cup V_2$ with $\bigl||V_1|-|V_2|\bigr|\le1$ such that \[ \min\{e(V_1,V_2),e(V_2,V_1)\} \ge \frac{d(m+d+1)}{2(2d+1)}. \] Here, for disjoint vertex sets $...

Zhaoyang Ma, Shu-Fei Wu, Qing-Hou Zeng · 0 citations
Preprint Sep 2026

Real-rootedness of the $\tau$-polynomial under graph joins

For a simple graph $G$ with $n$ vertices, write its chromatic polynomial in the rising factorial basis as $$ \chi_G(x)=\sum_{i=0}^{n}(-1)^{n-i}c_i(G)\langle x\rangle_i,$$ where $ \langle x\rangle_i=x(x+1)\cdots(x+i-1).$ The associated $\tau$-polynomial $$ \tau_G(x)=\sum_{i=0}^{n}c_i(G)x^i $$ was defined and systematica...

Ming-Yang Kang, Zhi-Xin Liu, Sophie C. C. Sun et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.