39 problems

Let $r,g\in \mathbb{N}$. A digraph $D$ has girth at least $g$ if its shortest directed cycle has length at least $g$, and let $\delta^+(D)$ denote its minimum out-degree. Caccetta–…

Behzad–Chartrand–Wall conjecture. Every $n$-vertex oriented digraph with minimum out-degree and minimum in-degree at least $n/3$ contains a directed triangle.

A digraph is Eulerian when it is strongly connected and every vertex has equal in-degree and out-degree. Its average out-degree is the average of the out-degrees of its vertices; d…

Let $G$ be a digraph, let $\beta(G)$ denote the minimum size of a feedback arc set, and let $\gamma(G)$ denote the number of non-adjacent unordered pairs of vertices of $G$. An $r$…

Let the perimeter gap of a digraph be the difference between its number of vertices and the length of its longest directed cycle. Bucić–Hendrey–Mohar–Steiner–Yepremyan's conjecture…

For a digraph $D$, let $c(D)$ be the largest integer $k$ for which there are directed cycles $C_1,\ldots,C_k$ through a common vertex $v$ such that $C_1-v,\ldots,C_k-v$ are pairwis…

Let $r\in\mathbb{N}$, and let $\delta^+(D)$ denote the minimum out-degree of a digraph $D$. A sequence $C_1,\ldots,C_r$ of directed cycles has at most one overlap per cycle if, for…

Let $l\geq 4$ be an integer, and let $k$ be the smallest integer greater than $2$ that does not divide $l$. Let $\delta^0(G)$ denote the minimum semi-degree of an oriented graph…

Let $c(n)$ be the minimum circumference of a connected vertex-transitive graph on $n$ vertices, and let $d(n)$ be the minimum circumference of a connected vertex-transitive digraph…

For a directed graph, its circumference is the maximum length of a directed cycle, and its perimeter gap is the difference between its order and its circumference. Linear perimeter…

Benhocine–Wojda degree-sum conjecture. If the sum of the degrees of every two nonadjacent vertices is at least $2p-1$, then $D$ contains $D(n,2)$ for each $n\in[3,p]$, except for c…

Let $t$ be a positive integer. An orientation of the cycle on $t$ vertices is obtained by assigning a direction to each edge of that cycle. Common degree conjecture. Every digraph…

Let $h(k,\ell)$ be the source's minimum-outdegree threshold for forcing $k$ vertex-disjoint directed cycles with $\ell$ different lengths. Weak finiteness conjecture. For every pos…

Let $D$ be a simple digraph with $n$ vertices, where every vertex except one has outdegree at least $r$. Let $\{s_1,t_1\},\ldots,\{s_r,t_r\}$ be $r$ distinct pairs of vertices in…

Seymour's non-uniform Caccetta–Häggkvist conjecture. $D$ contains a directed cycle of length at most

Let $C_k^\circlearrowright$ denote the directed cycle of length $k$, and let $D(G(n,p),C_k^\circlearrowright)$ be the number of orientations of $G(n,p)$ containing no copy of…

Let $G=(V,E)$ be a digraph on $n$ vertices, let $\beta(G)$ denote the minimum size of a feedback arc set, and let an $(r-1)$-free digraph be one containing no directed cycle of len…

Let $r$ be an even integer with $r\geq 4$, and let an $r$-free digraph be a digraph containing no directed cycle of length at most $r$. For a digraph $G$, let $\beta(G)$ be the min…

Let $D$ be an orientation of a planar graph. A vertex coloring of $D$ is without a monochromatic directed cycle if no directed cycle has all its vertices assigned the same color. N…

Let $D$ be a regular $c$-partite tournament, with $c\geq 5$. A $(p,|V(D)|-p)$-cycle-factor is a cycle-factor consisting of cycles of lengths $p$ and $|V(D)|-p$. Yeo's conjecture. F…

Let $D$ be a $k$-regular bipartite tournament, where $k$ is an integer greater than $2$, and let $u$ and $v$ be two specified vertices of $D$. Let $F_{4k}$ and the other specified…

Disjoint-union conjecture for oriented cycles. Any disjoint union of orientations of cycles is $\delta^+$-maderian.

Aboulker et al.'s cycle-orientation conjecture. Every orientation of a cycle is $\delta^+$-maderian.

Wang's conjecture. If $\delta^0(D)\geq (9k-3)/4$, then $D$ contains $k$ vertex-disjoint directed cycles, each of order at least $3$.

For positive integers $n$ and $r$, let $g(n,r)$ be the least integer such that every bipartite digraph $D$ with $n$ vertices in each part and minimum outdegree…