44 problems

Minimum-degree four conjecture. Every graph with minimum degree at least $4$ admits a majority edge colouring from lists of size $3$.

Let $G$ be a graph. For a list-assignment $L$ of $G$, an $L$-packing is a collection of mutually disjoint $L$-colourings, and it is proper if each colouring is proper. Let…

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

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…

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…

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…

A graph is $(3,1)$-choosable if every list assignment in which each list has size at least $3$ and the lists of adjacent vertices have intersection of size at most $1$ admits a pro…

Let $G$ be a graph, let $v(G)$ denote its number of vertices, and let $B_c[v]$ be the subgraph induced by the vertices at distance at most $c$ from $v$. For a positive integer $c$,…

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=(V,E)$ be a planar graph on $n$ vertices. A list assignment $L$ assigns a set $L(v)$ of colours to each vertex $v\in V$, and let $\mathcal{G}(G,L)$ be the graph whose vertic…

Independent-transversal packing conjecture.

List Colouring Conjecture. If $G$ is a graph of maximum degree $\Delta$ and $L$ is a list assignment to $E(G)$ such that

Let $G$ be a graph, and let $L$ be a $(k+1)$-list assignment of $G$, meaning that each vertex $v$ has a list $L(v)$ of $k+1$ available colours. Suppose that for every vertex $v$ of…

Local Vizing's theorem. There is an $L$-edge-colouring of $G$.

Let $G=(V=A\cup B,E)$ be a bipartite graph with maximum degrees on $A$ and $B$ at most $\Delta_A$ and $\Delta_B$, respectively. For positive integers $k_A$ and $k_B$, say that $G$…

Let $G$ be a bipartite graph with maximum degree at most $\Delta$, and let $k$ be a positive integer. The graph is $k$-choosable if every assignment of lists of $k$ colours to its…

Bounded-order list vertex arboricity conjecture. If

List colouring conjecture.