176 problems

Let $K_n$ be a complete graph whose edges are coloured with two colours. A monochromatic cycle is a cycle all of whose edges have the same colour. Lehel's conjecture. The vertex se…

Let $F$ be a finite graph. For an integer $k\geq 2$, call $F$ $k$-common if the minimum asymptotic density of monochromatic copies of $F$ in a $k$-edge-colouring equals the expecte…

Ge, Xu, and Zhang's conjecture. For every fixed $t$,

Let $G$ be a graph, let $k$ be an integer, and let $\Delta$ denote the maximum degree of $G$. A $k$-colouring of $G$ assigns one of $k$ colours to each vertex so that adjacent vert…

Let $G$ be a graph, let $\Delta(G)$ denote its maximum degree, and let $a'(G)$ denote the least number of colours in an acyclic edge colouring of $G$. Fiamčík–Alon–Sudakov–Zaks con…

Let $F(n;d4cd_{k,s}^{(1)})$ denote the maximum number of edge colourings avoiding monochromatic copies of $K_k$ over all $n$-vertex graphs. Erdős–Rothschild conjecture. The trivial…

Feder–Subi conjecture. For every $d \in \mathbb{N}$, every $2$-edge-colouring of $Q_d$ contains vertices $u,v$ with $\operatorname{dist}(u,v)=d$ that are connected by a path with a…

Let $G$ be a graph, let $r$ be a positive integer, and let $\alpha(G)$ denote the independence number of $G$. For an $r$-edge-colouring of $G$, let $\operatorname{cp}_r(G)$ be the…

Erickson's conjecture. The only values guaranteed to belong to $\mathcal{F}_{\Delta}$ for every $m$-colouring $\Delta$ are precisely $1$, $2$, and $m$.

Pardey–Rautenbach conjecture. There is a perfect matching $M$ of $K_{2kn}$ such that

Let $G$ be a cubic graph. A two-colouring of the vertex set is a partition of $V(G)$ into two colour classes, and each class induces a subgraph of $G$. Ando's conjecture. The verti…

Let $M$ be a loopless oriented matroid with no $M(K_4)$ minor. A Hadwiger conjecture for oriented matroids. $M$ has a nowhere-zero $3$-coflow. This is the first non-trivial open ca…

Unfriendly partition conjecture. Every countable graph admits an unfriendly bipartition.

Let $G$ be an $n$-vertex graph whose edges are coloured with two colours, and suppose that … A monochromatic cycle is a cycle all of whose edges have the same colour. Balogh–Barát–…

Let $Q_n$ be the $n$-dimensional hypercube with a red-blue edge-colouring, and call a path between antipodal vertices to have a colour change whenever consecutive edges have differ…

Let $Q_n$ be the $n$-dimensional hypercube, with antipodal vertices $v$ and $\bar v$ differing in every coordinate. Leader–Long conjecture. In every red-blue colouring of the edges…

Let $G$ be a graph. An orientation of $G$ is consecutively colourable if it has a proper arc colouring such that, for every vertex $v$, the colours of all out-arcs from $v$ and the…

Monotonicity conjecture. Under these conditions,

Grinshpun–Sárközy conjecture. For every positive integer $r$ there exists a constant $C_r$ such that, for every $\Delta\geq 2$ and every $\Delta$-bounded graph sequence…

Let $D$ be a digraph. A majority colouring of $D$ is a vertex colouring $c$ such that at least half of the out-neighbours of every vertex $v$ have a colour different from $c(v)$. K…

Distant total sum distinguishing conjecture. For every positive integer $r$ there exists a constant $C$ such that

Let $r\geq 3$ be an integer, and let $G$ be a graph without isolated edges and with maximum degree $\Delta$. Its $r$-distant sum distinguishing index $\chi'\_{\Sigma,r}(G)$ is the…

Let $G=(V,E)$ be a graph, and let $c:V\cup E\to\{1,2,\ldots,k\}$ be a proper total colouring. For each vertex $v$, define its total sum by … Let $\chi”_{\Sigma}(G)$ be the least…

Exact-value conjecture. Under these conditions,

Spanning cycle conjecture. For all $k,n \in \mathbb{N}$,