30 problems

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 $k$ and $g$ be positive integers, and let $f(k,g)$ be the minimum integer such that every finite simple digraph of girth $g$ and minimum outdegree at least $f(k,g)$ contains…

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–…

Let $D$ be a finite simple digraph, and let $f(k)$ be the minimum integer such that every digraph with minimum outdegree at least $f(k)$ contains $k$ vertex-disjoint directed cycle…

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.

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…

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…

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…

A digraph is a directed graph; it is Eulerian when it is strongly connected and every vertex has equal in-degree and out-degree. For a digraph $G$, let $A(G)$ denote its arc set, l…

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…

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 $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$.

A digraph is $p$-strongly connected when its strong connectivity is at least $p$. Lovász's conjecture. There exists an integer $p$ such that every $p$-strongly connected digraph ha…

Linear-backwards-edge conjecture. The following hold:

Let $D$ be an oriented bipartite graph with bipartition $(A,B)$, and let $d^+(x)$ denote the out-degree of a vertex $x$. A directed $C_4$ is a directed cycle of length four in $D$.…