72 problems

List Colouring Conjecture. For every graph $G$,

A list assignment $L$ of a graph is symmetric if its colours are integers and, for every vertex $v$ and integer $i$, $i\in L(v)$ implies that $-i\in L(v)$. A graph is weakly $k$-ch…

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

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

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 $G$ be a planar graph with no cycles of lengths $4$, $5$, or $6$. A graph is 3-choosable if it is colourable from every assignment of lists of size $3$. Montassier's conjecture…

Weak List Hadwiger conjecture. There is a constant $c$ such that every $K_t$-minor-free graph is $ct$-choosable.

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…

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…

A list assignment $L$ for a graph $G$ assigns a set $L(v)$ of permissible colours to each vertex $v$. The graph $G$ is $k$-choosable if every list assignment with $|L(v)|\geq k$ fo…

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

List colouring conjecture. For every graph $G$,

Let $G$ be an IC-Brooks graph, and let $cDelta(G)=r$. Here, $K_{r+1}^-$ denotes the complete graph $K_{r+1}$ with one edge removed. The IC-Brooks clique conjecture. The graph $G$ c…

Let $G$ be a graph embedded in a surface $\Sigma$, and let $g(\Sigma)$ denote the genus of $\Sigma$. A graph is $\rho$-locally planar if the relevant local planarity condition hold…

Let $G$ be a simple finite graph. Its edge-chromatic number is denoted by $\chi'(G)$, and its list edge-chromatic number by $\chi'_{\ell}(G)$. List colouring conjecture. … for any…

Given positive integers $k \leq m$, a random $(k,m)$-list-assignment assigns independently to each vertex a uniformly random $k$-element subset of $\{1,\ldots,m\}$. An $n$-vertex g…

Layered-tree-width weak-diameter conjecture. For every positive integer $w$, there exists a positive integer $N$ such that every graph with layered tree-width at most $w$ is 3-choo…

Layered-tree-width choosability conjecture. For every pair of positive integers $w$ and $\Delta$, there exists a positive integer $N$ such that every graph with layered tree-width…

Local palette-sparsification conjecture. The graph $G$ is $L$-colorable with high probability.

Palette-sparsification conjecture. The graph $G$ is $L$-colorable with high probability.

Packing version of Dinitz's problem. For $n\geq 3$,

Let $\lambda$ be a multiset of positive integers, let $k_\lambda$ be the sum of its elements, and let $|\lambda|$ be its number of elements. For a graph $G$, define $h(\lambda)$ to…

Let $K_t$ be the complete graph on $t$ vertices, and call a graph $K_t$-minor-free if it has no $K_t$ minor. A list assignment $L$ assigns a set of permissible colours $L(v)$ to ea…

Let $K_{n,n}$ be the complete bipartite graph with parts of size $n$. A random $(k,n)$-list assignment assigns independently and uniformly to each edge a $k$-element subset of…