143 problems

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…

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

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

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…

For a digraph $D$, a set of directed cycles has distinct lengths when no two of its cycles have the same length. Half-integral distinct-length directed-cycle conjecture. For every…

Converse-invariance conjecture. If

Distance-transitive Seymour-tightness conjecture. Every distance-transitive digraph is a Seymour-tight orientation.

Cayley classification conjecture. Every Seymour Cayley orientation can be constructed by taking, possibly repeatedly, lexicographic products of empty graphs, powers of directed cyc…

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

Approximate Seymour conjecture. For every $\epsilon>0$, every oriented graph $G$ has at least one vertex $v$ satisfying

Seymour's second neighbourhood conjecture. Every orientation $G$ contains at least one vertex $v$ 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…

The $C_4$-factor conjecture. There exists $n_0=n_0(\eta)\in\mathbb N$ such that, for every $n\geq n_0$ divisible by $4$, if

Let $T_1,T_2,\ldots$ be tournaments, and write $V(T_n)$ for the vertex set of $T_n$. Explicit tournament construction conjecture. There is an explicit construction of tournaments…

For integers $k\geq 2$ and $\ell\geq 1$, a $(k,\ell)$-spider is the $(k-1)$-subdivision of an in-star with $\ell$ leaves. A directed graph is considered with its minimum out-degree…

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…

Let $\mathfrak{g}$ be a complex finite-dimensional Lie algebra and $(\mathcal{M},\delta)$ an abelian magma such that $\mathfrak{g}$ is $\mathcal{M}$-magma-graded with finest granul…