59 problems

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

An oriented planar graph is a planar digraph with no digons, and its dichromatic number is the least number of colours in a vertex colouring in which every colour class induces an…

Let $G$ be a planar graph, and let $\vec{\chi}(G)$ denote the maximum, over all orientations of $G$, of the minimum number of acyclic colour classes in a vertex colouring. Neumann–…

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

Let $G$ be a simple planar graph and let $D$ be an orientation of $G$. The dichromatic number $\chi(D)$ is the smallest cardinal $\kappa$ such that $V(D)$ can be coloured with…

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

Aboulker–Charbit–Naserasr conjecture. For any hero $H$ and any oriented star forest $S$, oriented graphs containing neither $S$ nor $H$ as induced subdigraphs have bounded dichroma…

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

Critical-tournament finiteness conjecture. For every $k\in\mathbb{N}$, there is a finite number of $k$-critical tournaments.

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

Reed's digraph conjecture. 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…