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

…

Distinct-root conjecture. One has $\rho_1\neq\rho_2$. This asserts that distinct admissible parameter triples determine distinct spectral radii for the corresponding Type $5$ digra…

Conjecture on fixed-vertex extensions. For every fixed integer $k$, there exists a polynomial-time algorithm for deciding whether such a digraph has a Hamiltonian cycle.

Oriented Gyárfás–Sumner conjecture. For any oriented forest $\vv F$, $\operatorname{Forb}_{\mathrm{ind}}(\vv F)$ is dichromatically bounded.

Heroic-set conjecture. The set

Let $D$ be a strongly connected digraph with $n\geq 3$ vertices and $m$ arcs. An acyclic separator is a separator whose induced subdigraph is acyclic. Extremal arc-count conjecture…

A digraph $D$ is $k$-strong if it has at least $k+1$ vertices and remains strongly connected after the deletion of any set of at most $k-1$ vertices. An orientation of a digraph is…

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…

Jackson–Thomassen conjecture. Every $2k$-strong digraph has a spanning $k$-strong oriented subdigraph.

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…

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 digraph. Define … and let $\overset{\text{tiny}}{\leftrightarrow}{\omega}(D)$ be the largest size of a biclique in $D$. Let $\vec{\chi}(D)$ denote the dichromatic numb…

Exact asymptotic bound conjecture. For all $\delta\geq 1$ and $q\geq 3$,

Let $D$ be a digraph on $n\geq 3$ vertices, with nondecreasing out-degree sequence $d_1^+\leq\cdots\leq d_n^+$ and in-degree sequence $d_1^-\leq\cdots\leq d_n^-$. Nash-Williams' di…

Let $D$ be a strongly connected digraph on $n$ vertices, with nondecreasing out-degree sequence $d_1^+\leq\cdots\leq d_n^+$ and in-degree sequence $d_1^-\leq\cdots\leq d_n^-$. Nash…

Bounded-size inversion approximation hardness conjecture. There exists $\varepsilon>0$ such that, unless $P=NP$, for every $p\geq 3$ and every $k\geq 1$, no polynomial-time…

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…

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…

Let $r\in\mathbb{N}$, and let $\delta^+(D)$ denote the minimum out-degree of a digraph $D$. A sequence $C_1,\ldots,C_r$ of directed cycles has at most one overlap per cycle if, for…

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

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

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 $T$ be a tournament, let $D$ be a simple digraph on $n$ vertices with no subdigraph isomorphic to $T$, and let $\vec{\alpha}(D)$ denote its largest acyclic set. Strong Erdős–Ha…

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