318 problems

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 $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 digraph, and let $f4a0$ be the minimum out-degree parameter. For a digraph $F$, define $mader_{\delta^+}(F)$ to be the least integer $m$ such that every digraph $D$ wi…

Let $D$ be a digraph. For an integer $s\ge 1$, call a set $S\subseteq V(D)$ an $s$-source set if … where $N^-(S)$ is the set of external in-neighbors of $S$. For an integer…

Constancy conjecture. One has

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–Yeo conjecture. There exists an integer $K$ such that every $K$-arc-strong digraph has a strong arc decomposition.

Let $k_1,k_2,\dots,k_n$ be positive integers. A subdivision of an oriented cycle $C(k_1,k_2,\dots,k_n)$ is obtained by replacing each arc by a directed path of length at least $1$,…

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 and Yeo's conjecture. There exists an integer $K$ such that every $K$-arc-strong digraph has a strong arc decomposition.

Let the directed triangle mean the cyclic tournament on three vertices, and say that a tournament has the Strong Erdős–Hajnal property when it satisfies the strong Erdős–Hajnal con…

Let $D$ be a digraph. A stable set is a set of pairwise non-adjacent vertices, and a path partition is a collection of disjoint paths containing every vertex of $D$ exactly once. A…

Resistance-distance conjecture. The resistance distance is bounded above by the directed distance:

McDiarmid–Mohar conjecture. Every oriented graph $D$ satisfies

Dijoin additivity conjecture. The equality

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

For a tournament $T$ on $k$ vertices, let $g(k)$ be the largest integer such that every such tournament contains an acyclic subgraph with chromatic number $g(k)$. Nassar–Yuster con…

Let $J(n,k)$ be the Johnson digraph. Johnson digraph dichromatic-number conjecture. The dichromatic number satisfies … The paper gives only a heuristic for the upper bound and stat…

Darbinyan's degree conjecture. If $p-1$ vertices in $V(D)$ have degrees at least $p$, then $D$ contains a Hamiltonian bypass.

Let $D(q;m,n)=D_2(\mathbb F_q;X^mY^n)$ be a monomial digraph over the field with $q$ elements. Kodess's conjecture. For a prime power $q$, the digraphs $D(q;m_1,n_1)$ and…

Harutyunyan–Mohar conjecture. Every oriented graph $D$ satisfies

Let $D$ be a $k$-dicritical oriented graph on $n$ vertices, and let $m(D)$ denote its number of arcs. Hoshino–Kawarabayashi conjecture. For every integer $k\geq3$, … Hoshino and Ka…

Kostochka–Luo–Shan conjecture. Every digraph $D$ has a quasi-kernel of size at most

Let $D$ be a digraph, and let $\rho(D)$ and $\pi(D)$ denote its remoteness and proximity, respectively. Regularity conjecture. If … then $D$ is regular. The preceding result proves…