ﻻ يوجد ملخص باللغة العربية
Caccetta-Haggkvist conjecture is a longstanding open problem on degree conditions that force an oriented graph to contain a directed cycle of a bounded length. Motivated by this conjecture, Kelly, Kuhn and Osthus initiated a study of degree conditions forcing the containment of a directed cycle of a given length. In particular, they found the optimal minimum semidegree, i.e., the smaller of the minimum indegree and the minimum outdegree, that forces a large oriented graph to contain a directed cycle of a given length not divisible by $3$, and conjectured the optimal minimum semidegree for all the other cycles except the directed triangle. In this paper, we establish the best possible minimum semidegree that forces a large oriented graph to contain a directed cycle of a given length divisible by $3$ yet not equal to $3$, hence fully resolve the conjecture of Kelly, Kuhn and Osthus. We also find an asymptotically optimal semidegree threshold of any cycle with a given orientation of its edges with the sole exception of a directed triangle.
We show that, in almost every $n$-vertex random directed graph process, a copy of every possible $n$-vertex oriented cycle will appear strictly before a directed Hamilton cycle does, except of course for the directed cycle itself. Furthermore, given
Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We establish a corresponding result for fixed ev
In 1976, Steinberg conjectured that planar graphs without $4$-cycles and $5$-cycles are $3$-colorable. This conjecture attracted numerous researchers for about 40 years, until it was recently disproved by Cohen-Addad et al. (2017). However, coloring
We prove that there exists a function $f:mathbb{N}rightarrow mathbb{R}$ such that every digraph $G$ contains either $k$ directed odd cycles where every vertex of $G$ is contained in at most two of them, or a vertex set $X$ of size at most $f(k)$ hitt
We prove for all $kgeq 4$ and $1leqell<k/2$ the sharp minimum $(k-2)$-degree bound for a $k$-uniform hypergraph $mathcal H$ on $n$ vertices to contain a Hamiltonian $ell$-cycle if $k-ell$ divides $n$ and $n$ is sufficiently large. This extends a result of Han and Zhao for $3$-uniform hypegraphs.