236 problems

All graphs considered are finite, simple, and undirected. For a graph $G$, let $\chi(G)$ and $\omega(G)$ denote its chromatic number and clique number. If $H$ is a graph, then $G$…

Erdős–Nešetřil conjecture. Every graph $G$ satisfies

Wu–Zhang–Li conjecture. If

Jaeger–Swart conjecture. There are no cyclically $7$-edge-connected snarks.

Defective list edge-colouring conjecture. For every graph $G$ and every integer $d$,

Let $G$ be a finite, undirected, loopless graph with no parallel edges, and let $\Delta$ be its maximum degree. A proper edge colouring $c$ of $G$ is adjacent vertex distinguishing…

Grimmett–McDiarmid conjecture. With high probability, the chromatic number satisfies

A simple planar signed graph is a signed graph whose underlying graph is simple and planar, and a graph is 0-free 4-colourable if it admits a zero-free colouring with four colours.…

Stahl's conjecture. For all $q\ge1$ and $0\le r\le k-1$, one has

Odd-defect list edge-colouring conjecture. For every odd integer $d$ and for every graph $G$,

Let $G(n,\alpha)$ be the random Borsuk graph in dimension $d$, and let $\chi(G(n,\alpha))$ denote its chromatic number. Logarithmic threshold conjecture. For every $d\geq 2$ there…

Let $G(n,\alpha)$ be the random Borsuk graph in dimension $d$, with chromatic number denoted by $\chi(G(n,\alpha))$. For a monotone graph property, a sharp threshold is a threshold…

Let $G$ be a connected graph with $n$ vertices, and let $L$ be a list-assignment of $G$. Write $\mathcal{C}(G,L)$ for the $L$-recolouring graph and $\widehat{\mathcal{C}}(G,L)$ for…

Let $\widehat{\mathit{SS}}(n,k)$ be the signed Schrijver graph, and consider any signed graph switching-equivalent to it. The negative-edge-induced graph is the graph whose edges a…

Lužar–Škrekovski conjecture. For every planar graph $G$ with maximum degree $\Delta$ it holds that

Aravind–Subramanian conjecture. There exists a constant $C$ such that

Harutyunyan–Mohar conjecture. Every oriented graph $D$ satisfies

List distinguishing index conjecture.

A graph $G$ has vertex set $V(G)$ and edge set $E(G)$. A total-colouring assigns colours to the vertices and edges of $G$ so that no adjacent or incident elements receive the same…

Let $n$ be a positive integer, and for each $1\leq i,j\leq n$, let $S_{ij}$ be a set of size $n$. A partial latin square is an $n\times n$ array in which all entries in any row or…

Let $G$ be a graph. The list edge colouring conjecture. For every graph $G$, the edge choice number equals the edge chromatic number: … This conjecture asserts that list edge colou…

Fractional chromatic number conjecture. The fractional chromatic number of every triangle-free cubic graph is at most

Let $G$ be a 3-connected non-complete planar graph. The graph is degree-truncated $k$-choosable when it is $f$-choosable for the function $f(v)=\min\{k,d_G(v)\}$. Degree-truncated…

Degree-truncated 10-choosability conjecture. Every 3-connected non-complete planar graph is degree-truncated $10$-choosable. Consequently,

The dominating Hadwiger conjecture. Every graph with no dominating $K_t$-model is $(t-1)$-colourable.