134 problems

For every integer $k\ge 2$, every graph $G$ with odd girth $\operatorname{og}(G)\ge 2k+1$ and maximum average degree $\operatorname{mad}(G)<2+1/k$ admits a $(2k+1:k)$-coloring; tha…

Chen–Lih–Wu conjecture.

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 graph is $k$-colourable if it has a proper colouring using at most…

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…

Minor-closed-family conjecture. There exists a function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that $f(n)=n^{1+o(1)}$ and, for every minor-closed family of graphs $\mathcal{G}$,

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

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

Let an oriented graph be a digraph with no pair of oppositely directed parallel arcs, and let its maximum average degree be the maximum of $2|A(H)|/|V(H)|$ over all non-empty subdi…

Let $G$ be a connected graph of order at least three, different from the cycle $C_5$. Write $\chi'_{\sum}(G)$ for its neighbour sum distinguishing index and $\Delta(G)$ for its max…

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

Caro–Petru1evski–skrekovski's conjecture. For every connected graph $G$ of maximum degree $\Delta\geq 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 at least three vertices. An edge weighting assigns a weight from $\{1,2,3\}$ to every edge of $G$, and the sum at a vertex is the sum of the weigh…

Polynomial-time k-colouring conjecture. There is a polynomial-time algorithm that, given $G$, finds a $k$-colouring of $G$, or determines that none exists.

Eventual odd circular mixing conjecture. There exists an integer $q_0$ such that, for every integer $q\geq q_0$, the graph $G$ is $(2q+1,q)$-mixing.

Let $G$ be a graph, let $\Delta(G)$ denote its maximum degree, and let $P(G,t)$ be its chromatic polynomial. Sokal's conjecture. … for every complex number $t$ satisfying … This wo…

Let $\mathcal T$ be a locally finite tiling with a finite number of polygonal prototiles. Suppose … is a partition into translations of finitely many, not necessarily distinct, fin…

Zhang–Zhang conjecture. If

Meyer's conjecture.

Let $G(n,\alpha)$ be the random Borsuk graph in dimension $d$, let $\chi(G(n,\alpha))$ denote its chromatic number, and let $\alpha_0$ be the constant supplied by the Erdős–Hajnal…

Fix $d\geq 2$ and $k\in\{3,\dots,d+1\}$. In the random Borsuk graph process, edges are added in order of decreasing geodesic distance as the angle parameter $\alpha$ increases. For…

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

Let $G$ be a finite simple graph, and let a model consist of pairwise vertex-disjoint connected branch sets, with adjacent branch sets joined by an edge. Seymour's half-order match…