7 problems

Let $G$ be a graph, let $k$ be an integer, and let $\Delta$ denote the maximum degree of $G$. A $k$-colouring of $G$ assigns one of $k$ colours to each vertex so that adjacent vert…

Kempe-equivalence conjecture. The graph $G$ is perfectly contractile if and only if, for every replication graph $H$ of an arbitrary induced subgraph of $G$ and every…

Degree-swappability conjecture. Every $3$-connected graph distinct from the complete graph and the triangular prism is degree-swappable.

Let $K_p$ be the complete graph on $p$ vertices. A frozen $p$-colouring is a proper $p$-colouring in which every pair of colour classes induces a connected subgraph; equivalently,…

For a graph $G$, a $t$-colouring is a proper colouring using $t$ colours, and two colourings are Kempe equivalent when they are connected by a sequence of Kempe changes, each swapp…

Let a quintic graph be a 5-regular graph, and let two 1-factorisations be Kempe equivalent if one can be obtained from the other by a sequence of Kempe switches. Kempe-class conjec…

Subcubic conjecture. If $G$ is subcubic, meaning that $\Delta\leq 3$, then