237 problems

Let $D=(V,A)$ be a digraph. A dicut is a set of arcs $delta^+(U)$ leaving a nonempty proper vertex subset $U$ with $delta^-(U)=emptyset$, and a dijoin is an arc subset intersecting…

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 $G$, let $\operatorname{girth}(G)$ be the length of a shortest directed cycle. Define $\beta(G)$ to be the least number of arcs whose deletion makes $G$ acyclic, and…

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

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 $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 $V$ be a finite set, let $G=(V,E)$ be a directed graph, and let … where $\varepsilon_G(i,j)=1$ if $(i,j)\in E$ and $0$ otherwise, and let $c\mathscr{A}_m(G)$ be its cone. A tot…

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…

Pokrovskiy's conjecture. There exists an integer $f(k)$ such that every $2k$-strong tournament with minimum semi-degree at least $f(k)$ is $k$-linked.

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.

Let $G$ be a regular tournament on $n$ vertices, and let $B(G)$ denote its brushing number. Regular-tournament brushing conjecture. If $G$ is regular, then … This extends the estab…

Let $G_{m,n}=P_m\Box P_n$ be the Cartesian product of paths on $m,n\geq 2$ vertices. Let ${D}_{m,n}$ be the orientation of $G_{m,n}$ with all $P_m$-layers oriented up except the la…

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…

Branching component graph product conjecture. The branching component graph satisfies

Behzad–Chartrand–Curtis conjecture. The order of $D$ 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…

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$, and let $u$ and $v$ be distinct vertices of $X$. Ham…

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

Zhou and Li's conjecture. The same equality should hold whenever $n\geq 3k$; moreover, the extremal digraphs should be precisely the transitive Turán digraphs…

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…

The New Digraph Reconstruction Conjecture. The source proposes a directed reconstruction conjecture based on the collection of these triples, asserting that this augmented vertex-d…

Let $G$ be a graph, and let $A_n(G)$ denote its $n$-th A-group, an analogue of the $n$-th homotopy group of a topological space. Let $|N_1G|$ be the geometric realization of the cu…