144 problems

For every integer $k\ge 2$, every oriented graph $G$ with minimum semidegree $\delta^0(G):=\min\{\delta^+(G),\delta^-(G)\}>k/2$ contains, as a subgraph, every orientation of the pa…

Given a semicomplete digraph $D$ and distinct vertices $x,y\in V(D)$, determine a longest directed $(x,y)$-path. Given a locally semicomplete digraph $D$ and distinct vertices…

Directed Linear Arboricity Conjecture. For every directed graph $D$,

Seymour's second neighbourhood conjecture. Every orientation $G$ contains at least one vertex $v$ such that

For a digraph $D$, its minimum out-degree is the minimum number of outgoing edges over all vertices of $D$. Lichiardopol's conjecture. For every $k\geq1$, there exists an integer…

Let $\mathfrak{g}$ be a finite-dimensional $k$-step nilpotent Lie algebra. Nilpotent minimal-graph-admissibility conjecture. If $k\leq 2$, then $\mathfrak{g}$ is minimal-graph-admi…

Sullivan's conjecture. Every oriented graph contains at least one vertex $v$ such that

Let $G$ be a directed $d$-regular graph on $n$ vertices, and regard a cycle as a directed cycle, with an individual edge allowed to count as a cycle of length two as in the source.…

Let $D$ be a digraph, let $k$ be a positive integer, and write $\delta^{+}(D)$ for its minimum out-degree. A transitive tournament on $k$ vertices is the tournament whose vertices…

Kühn–Osthus conjecture. The digraph $G$ contains a Hamilton cycle. The source introduces this as the digraph analogue of the $t=2$ case of the Bollobás–Häggkvist conjecture; no res…

Lee, Loh and Sudakov's conjecture. Every digraph $D$ with minimum outdegree at least $d+1$ admits a bipartition $V(D)=V_1\cup V_2$ such that

Let $\tau\textgreater=2$ be an integer, and let $D=(V,A)$ be a digraph whose minimum dicut size is $\tau$. A strengthening is an arc set whose reversal makes the digraph strongly con…

Large flame extension conjecture. In every $r$-rooted digraph $D$, every flame extends to a large flame. In particular, every $r$-rooted digraph $D$ admits a large flame.

Alspach et al.'s wreath-product conjecture. If $G$ and $H$ are hamiltonian decomposable directed graphs, then $G\wr H$ is also hamiltonian decomposable.

An oriented graph is a directed graph without loops or multiple edges. For an oriented graph $G$, let $\delta^\pm(G)$ be its minimum semidegree, the smaller of its minimum indegree…

Athanasiadis's freeness conjecture. The coning $c\mathcal{A}_G$ is free if and only if $G$ satisfies (A1) and (A2).

The bunkbed conjecture for transitive tournaments. The statement

Weaker dijoin decomposition conjecture. The arc set $A$ can be decomposed into a $k$-dijoin and a $(\tau-k)$-dijoin, for every $k\in\{1,\ldots,\tau-1\}$.

Let $D$ be a non-empty digraph. For a vertex $u\in V(D)$, let $d^+(u)$ denote its out-degree, let $N^+[u]$ denote its closed out-neighborhood, and call a vertex a source if it has…

Let $C_n$ denote the directed cycle of order $n$, and let $b3_I(D)$ be the Italian domination number of a digraph $D$. For an odd integer $n$, Kim's conjecture. … This conjecture c…

Branching component graph product conjecture. The branching component graph satisfies

Let $X$ be the Cartesian product of $k$ directed cycles of lengths $m_1,m_2,\ldots,m_k$, where $k\geq 3$ and each $m_i\geq 2$. For vertices $u$ and $v$ of $X$, let $d_X(u,v)$ denot…

Fixed-degree counting conjecture. The counting problem … is $\#P$-complete on the class of primitive $k$-out graphs, and remains $\#P$-complete for fixed out-degree $k$, already fo…

Random totally simple graph conjecture. One has … Moreover, for fixed $n$, the function … is nondecreasing. More quantitatively, there exist constants $c_k>0$ and…

DeBiasio's conjecture. Every $n$-vertex digraph $D$ satisfying