234 problems

Let $D$ be an orientation of a complete multipartite graph, and let $r$ be the number of its parts having odd size. Write $A_D(t)$ for the Eulerian polynomial of $D$, and let…

For every integer $k\ge 1$, every $2k$-strong digraph $D$ has a spanning subdigraph $H$ such that $H$ is oriented and $k$-strong; equivalently, $V(H)=V(D)$, $A(H)\subseteq A(D)$,…

For all positive integers $n$ and $k$, every digraph $D$ on $n$ vertices with more than $(k-1)n$ arcs contains every antidirected tree $T$ with $k$ arcs as a subdigraph. Here, an a…

Given a digraph $D=(V,A)$, determine whether there is a partition $A=A_1\mathbin{\dot\cup}A_2$ such that one of the following holds: (i) $D[A_1]$ is a perfect matching and $D[A_2]$…

For each fixed integer $d\ge 1$, determine the largest function $F_d(m)$ such that, for every sufficiently large integer $m$ and every digraph $D$ with $m$ arcs and minimum semideg…

…

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…

List Erdős–Neumann-Lara conjecture. For every integer $k$ there is an integer $f(k)$ such that, for every graph $G$, $\chi_{\ell}(G)\geq f(k)$ implies $\vec\chi_{\ell}(G)\geq k$.

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 $q$ be a prime power, and let $m_1,n_1,m_2,n_2$ be integers from $\{1,2,\ldots,q-1\}$. For a monomial digraph $D(q;m,n)$, write $D_1=D(q;m_1,n_1)$ and $D_2=D(q;m_2,n_2)$. The m…

For every positive integer $a$ and every finite digraph $D$, if $D$ is $(a+1)$-strongly connected and $4\alpha_2(D)\le a\u00024$, where $4\alpha_2(D)\u00024$ is the maximum cardina…

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

A graph $G=(V,E)$ is $k$-connected if it remains connected after the deletion of any set of at most $k-1$ vertices. An orientation of $G$ is $k$-strong if its corresponding digraph…

Let $D$ be a source-free bipartite digraph, meaning that every vertex has a nonempty set of external in-neighbors. A quasikernel of $D$ is an independent set $Q\subseteq V(D)$ such…

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…

Thomassen's conjecture. There exists an integer $K$ such that every $K$-arc-strong digraph $D=(V,A)$ has a good $(u,v)$-pair for every choice of $u,v\in V$.

Let $F$ be an acyclic digraph, and let $\delta^+(D)$ denote the minimum out-degree of a digraph $D$. A subdivision of $F$ is obtained by replacing the arcs of $F$ by directed paths…

Magnant–Martin's strengthened conjecture. If $G$ is a $d$-regular digraph on $n$ vertices, then

Erdős–Neumann-Lara conjecture. For every integer $k$ there is an integer $f(k)$ such that, for every graph $G$, $\chi(G)\geq f(k)$ implies $\vec\chi(G)\geq k$.

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.

Bang-Jensen and Yeo's conjecture. There exists an integer $K$ such that every $K$-arc-strong digraph has a strong arc decomposition.

Let $d_k(n)$ be the minimum number of arcs in a $k$-dicritical digraph of order $n$, and let $o_k(n)$ be the minimum number of arcs in a $k$-dicritical oriented graph of order $n$,…

Bang-Jensen–Yeo's conjecture. There exists an integer $K$ such that every $K$-arc-strong digraph $D=(V,A)$ has an arc-partition

Let $D$ be a digraph. A majority colouring of $D$ is a vertex colouring $c$ such that at least half of the out-neighbours of every vertex $v$ have a colour different from $c(v)$. K…

Linial's conjecture. For every digraph $D$ and every positive integer $k$,