46 problems

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

A tournament $H$ is a champion if there exists an integer $c_H$ such that every $H$-free tournament has acyclic dichromatic number at most $c_H$. The notation $TT_k$ denotes the tr…

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

Let $\mathcal{C}$ be a class of tournaments, where a tournament is an orientation of a complete graph. Let $\mathcal{C}^{subst}$ denote the closure of $\mathcal{C}$ under substitut…

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

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

Tournament acyclic dicolouring algorithm conjecture. For every fixed $k\geq3$, it is polynomial-time decidable whether a tournament $T$ satisfies

Planar acyclic dichromatic conjecture. Every oriented planar graph $D$ satisfies

Local-to-global conjecture. There exists a function $f\colon \mathbb{N}\to\mathbb{N}$ such that every tournament $T$ satisfies

The acyclic hero conjecture. A tournament $H$ is an acyclic hero if and only if $H\in\mathcal{AH}$.

Let $D$ be a digraph with maximum out-degree $\Delta^+(D)$, biclique number $\overset{\leftrightarrow}{\omega}(D)$, and dichromatic number $\vec{\chi}(D)$. Write…

Let $D$ be a digraph, let … let $\overset{\leftrightarrow}{\omega}(D)$ be the biclique number, and let $\vec{\chi}(D)$ be the dichromatic number. Write…

Let $D$ be a digraph. Define its maximum geometric-mean degree by … let $\overset{\leftrightarrow}{\omega}(D)$ be its biclique number, and let $\vec{\chi}(D)$ be its dichromatic nu…

Biclique corollary conjecture. There exists $\varepsilon>0$ such that every digraph $D$ satisfies

Directed-clique conjecture. There exists $\varepsilon>0$ such that every digraph $D$ satisfies

For each positive integer $n$, let $\vec t(n)$ be the maximum dichromatic number of an oriented triangle-free graph of order $n$. Maximum dichromatic number conjecture. … This conj…

Let $H$ be an oriented graph, and let an $H$-free oriented graph be one that does not contain $H$ as a not necessarily induced subdigraph. For an oriented graph $D$, write…

Let $T$ be a tournament and suppose that one of its backedge graphs is a forest. For a tournament, let its clique number mean the minimum clique number of a backedge graph over all…

Tournament Gyárfás–Sumner conjecture. If $T$ has a backedge graph that is a forest, then the class of tournaments not containing $T$ as a subgraph is dichromatically bounded by cli…

Let $F$ be a digraph with maximum degree $\Delta$. For an integer $g$, let $\mathrm{mader}_{\vec{\chi}}^{(g)}(F)$ be the least integer $k$, if it exists, such that every digraph…

Let $F$ be a digraph, and let $\mathrm{mader}_{\vec{\chi}}(F)$ be the least integer $k$ such that every digraph $D$ with dichromatic number $\vec{\chi}(D)\geq k$ contains a subdivi…

A class of digraphs $\mathcal C$ is dichromatically bounded if its dichromatic number is bounded as a function of its clique number. The substitution conjecture. If a class of digr…

A class of tournaments $\mathcal T$ has the $BIG\Rightarrow BIG$ property if there exists a function $f$ such that, for every $T\in\mathcal T$, if…

Let $k\geq 1$. A tournament has twin-width at most $k$ if its twin-width is at most $k$. The bounded twin-width conjecture. The class of tournaments with twin-width at most $k$ is…