93 problems

Frankl–Győri–He–Lv–Salia–Tompkins–Varga–Zhu conjecture. As $n$ tends to infinity,

Polynomial mixing-time conjecture. For any graph $G$, the Glauber dynamics on the $k$-colourings of $G$ for $k\geq\Delta+2$ has polynomial mixing time.

Exact-value conjecture. Under these conditions,

Feder–Subi conjecture. Every 2-colouring of $E(Q_n)$ contains a path between some pair of antipodal vertices which changes colour at most once.

In ZF, let a cardinal number be defined as an equivalence class under equinumerosity. For a graph, its chromatic index is the least cardinal number of colours in a proper edge-colo…

Let $G$ be a graph and let $G\xrightarrow{\operatorname{odd}} K_{ct}$ mean that $G$ admits a $t'$-oddomorphism to $K_{ct}$, as defined in the source. Linear immersion conjecture. T…

Strengthened cycle-free chromatic discrepancy conjecture. For every integer $\ell\ge 3$, every $C_{\ell+1}$-free graph $G\ne K_{\ell}$ satisfies

Cycle-free chromatic discrepancy conjecture. For every integer $\ell\ge 2$, every $C_{\ell+1}$-free graph $G$ satisfies

Let $k$ be a positive integer. A $0_{q(k)}$-graph is the graph class defined in the source, and $\chi'_k(G)$ is the mod $k$ chromatic index. $0_{q(k)}$-graph conjecture. For every…

Let $k$ be a positive integer. A $0_k$-graph is the graph class defined in the source, and $\chi'_k(G)$ is the mod $k$ chromatic index. $0_k$-graph conjecture. For every $0_k$-grap…

Let $G$ be an antiferromagnetic graph, and let $H$ be any graph. Universal bipartite-swapping conjecture. Then … Here $H\times K_2$ is the categorical product with the two-vertex c…

Let $H$ be a graph and let $q\geq 2$. Write $K_q$ for the complete graph on $q$ vertices, and let $H\times K_2$ denote the categorical product with the two-vertex complete graph. Z…

Multicoloured Erdős–Hajnal conjecture. For all $1\le s_0\le s$ and $k\ge1$, and every $s_0$-colouring $c_0$ of $K_k$, there exist $\delta,C>0$ such that, for all $n\in\mathbb N$ an…

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

The authors' conjecture. For each integer $n\geq 3493$, if $n\geq 2m+499$ and $m\geq 7$ is an odd integer, then

List strengthening conjecture. For every integer $k\geq 2$, if a graph $G$ has minimum degree $\delta(G)\geq k^2$, then $G$ has a $1/k$-majority edge colouring from any lists of si…

Majority edge-colouring conjecture. For every integer $k\geq 2$, if a graph $G$ has minimum degree $\delta\geq k^2$, then $G$ is $1/k$-majority edge $(k+1)$-colourable.

Let $G$ be a graph of order $n$, let $\overline{G}$ be its complement, and choose $\pi\in\{\operatorname{gp},\operatorname{mp}\}$, where $\operatorname{gp}$ and $\operatorname{mp}$…

Mohr–Pardey–Rautenbach's conjecture. Fix integers $k,n\geq 1$ such that $\binom{n}{2}$ and $(k-1)n/k$ are both even integers. If $\mathbf{c}:E(K_n)\to\{-1,1\}$ is a 0-sum labeling…

Mohr–Pardey–Rautenbach conjecture. There exists a copy $F'$ of $F$ in $K_n$ such that

Clique uniqueness conjecture. For every positive integer $t\geq 2$,

Ge–Xu–Zhang conjecture. For every positive integer $t\geq 4$ with $t\equiv 0,1\pmod 4$,

Versteegen's conjecture. We have

Let $G$ be sampled from the binomial random graph $G_{n,1/2}$, and let $\chi(G)$ and $\zeta(G)$ denote its chromatic and cochromatic numbers, respectively. Here, “with high probabi…

Eventual chromatic spectrum conjecture. For every integer $\delta\geqslant 3$, there exists an integer $v_0$ such that whenever $v\geqslant v_0$ and $v\equiv 3\pmod{6}$, there is a…