115 problems

Asymptotic coloring conjecture. As $s\rightarrow\infty$,

Let $k\in\mathbb{N}$ and let $D_1,\dots,D_k$ be oriented graphs satisfying … Write $[D_1,\dots,D_k]$ for their join, and let $\operatorname{inv}$ denote inversion number. Dijoin co…

Vertex-deletion conjecture. There exists $v\in V(D)$ such that

Dijoin counterexample-range conjecture. For all $\ell,r\in\mathbb{N}$ with $\ell\geq 3$ or $r\geq 3$, there exist oriented graphs $L$ and $R$ such that

Dijoin conjecture.

The all-$k$ dijoin counterexample conjecture. For any $k\geq3$, there is a tournament $T_k$ with $\operatorname{inv}(T_k)=k$ such that

Alon's inversion-number partition conjecture. For every two positive integers $k_1,k_2$, there exists an integer $f(k_1,k_2)$ such that every oriented graph $D$ with

Bang-Jensen et al.'s complexity conjecture. Deciding whether a given digraph $D$ has inversion number at most $k$ is NP-complete for any fixed positive integer $k$.

Bang-Jensen et al.'s tightness conjecture. For every positive integer $n$, there exists an oriented graph $D$ such that

The $Q_n$ inversion-number conjecture.

Belkhechine et al.'s inversion-number conjecture.

Asymptotic upper-bound conjecture.

Conjecture on oriented-graph speeds. This predicts a jump from polynomial to at least factorial speed for unlabelled hereditary properties of oriented graphs. The paper poses it as…

Let $G$ be an oriented graph. Its minimum pseudo-semidegree $\bar{\delta}^0(G)$ is the minimum among all non-zero in-degrees and out-degrees of its vertices; equivalently, it is th…

Let $G$ be an oriented graph, and let $4\delta^0(G)4$ denote its minimum semidegree, the minimum of the in-degree and out-degree over all vertices. An oriented path of length…

Let $T$ be a tournament, namely an oriented graph in which every pair of distinct vertices is joined by exactly one directed arc. For a vertex $x$, let $N_T^+(x)$ and $N_T^{++}(x)$…

Let $D$ be an oriented graph. For a vertex $x$, let $N_D^+(x)$ and $N_D^{++}(x)$ denote its out-neighborhood and second out-neighborhood, respectively. A complete matching from $X$…

Let $D$ be an oriented graph, and let $\Delta$ be the maximum degree of the underlying graph of $D$. Let $\vec{\chi}(D)$ denote its dichromatic number. Erdős–Neumann-Lara conjectur…

Let $T$ be an orientation of a tree with maximum degree at least $3$. An oriented graph $D$ is converse invariant if $f_T(D)=f_T(\overline{D})$ for every tournament $T$, where…

Let $D_1$ and $D_2$ be non-isomorphic oriented paths. Their chromatic noncommutative symmetric functions are denoted by $\mathbf{X}_{D_1}$ and $\mathbf{X}_{D_2}$, respectively. Ori…

Let $l\geq 4$ be an integer, and let $k$ be the smallest integer greater than $2$ that does not divide $l$. Let $\delta^0(G)$ denote the minimum semi-degree of an oriented graph…

Cycle-factor extension conjecture. If

Ai–Guo–Freschi–Lo conjecture. Let $G$ be an oriented graph on $n\geq 3$ vertices. If $\sigma_2(G)\geq n$, then $G$ contains a Hamilton cycle $C$ such that

Let $D$ be an oriented graph with $n$ vertices and $m$ edges or arcs, and let $\vec{\alpha}(D)$ denote its largest acyclic set. Aharoni–Berger–Kfir conjecture. … For tournaments th…

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…