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 $\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....
For a graph $G$, let $e(G)$ denote the number of edges of $G$, and let $c(G)$ be the number of distinct cycles in $G$. Morrison, Roberts and Scott asked whether, for every fixed graph $H$ and all large $n$, some $n$-vertex $H$-free graph maximizes both $e(G)$ and $c(G)$. In this paper, we show that the answer is no for...
The \emph{ordered Ramsey number} $r_<(G,H)$ of ordered $k$-graphs $G$ and $H$ is the least integer $N$ such that every red-blue edge-coloring of the naturally ordered complete $k$-graph on $[N]$ contains a blue ordered copy of $G$ or a red ordered copy of $H$. We prove that there is an absolute constant $c>0$ such that...
Wen Chen, Zi-Han He, Qi-Zhong Lin et al.· 0 citations
For a nonempty acyclic oriented graph $H$, let $p(H)$ be the order of a longest directed path and let $\tau(H)$ be the least positive integer $n$ such that $H$ admits a homomorphism to every tournament of order $n$. For all $p\ge3$ and $g\ge1$, we construct a connected acyclic oriented graph $H$ with underlying girth g...
For a graph $H$, the anti-Ramsey number $\operatorname{ar}(n,H)$ is the maximum number of colors in an edge-coloring of $K_n$ containing no rainbow copy of $H$, where a copy is rainbow if its edges have pairwise distinct colors. Let $s,t$ be nonnegative integers with $s+t\ge2$, and let $H_{s,t}$ be a graph consisting o...
An equitable $k$-coloring of a graph partitions its vertex set into $k$ independent sets whose sizes differ by at most one; the least such $k$ is the equitable chromatic number $\chie(G)$. Every known bound on $\chie$ valid for all graphs, beginning with the Hajnal--Szemer\'edi theorem, is linear in the maximum degree...
Mohammad F. Marashdeh· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
