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…

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

Chen–Lih–Wu conjecture.

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

Let $G$ be a finite graph, let $T$ be a forest, and write $\chi(G)$ for the chromatic number and $\omega(G)$ for the clique number. Polynomial Gyárfás–Sumner conjecture. For every…

Bounded-mad backbone colouring conjecture.

Backbone colouring conjecture.

Let $D$ be a digraph, let … let $\overset{\leftrightarrow}{\omega}(D)$ be the biclique number, and let $\vec{\chi}(D)$ be the dichromatic number. Write…

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…

Perfect-or-bounded-clique-width conjecture. One of the following holds:

Exponential average-availability conjecture. There exists a constant $c>1$ such that, for every planar graph $G$ and local girth function $f$ for $G$, there is a legal sequence of…

Let $\mathcal{G}_{n,3}$ be the random $3$-regular graph on $n$ vertices, and let $s(G)$ denote the smallest size of a Sudoku set for a graph $G$. Here, a Sudoku set is a vertex sub…