A recolouring sequence, between k-colourings α and β of a graph G, transforms α into β by recolouring one vertex at a time, such that after each recolouring step we again have a proper k-colouring of G. The diameter of the k-recolouring graph, diam C_k(G), is the maximum over all pairs α and β of the minimum length of a recolouring sequence from α to β. Much previous work has focused on determining the asymptotics of diam C_k(G): Is it Θ(|G|)? Is it Θ(|G|²)? Or even larger? Here we focus on graphs for which diam C_k(G) = Θ(|G|), and seek to determine more precisely the multiplicative constant implicit in the Θ. In particular, for each k ≥ 3, for all positive integers p and q we exactly determine diam C_k(K_p,q), up to a small additive constant. We also sharpen a recolouring lemma that has been used in multiple papers, proving an optimal version. This improves the multiplicative constant in various prior results. Finally, we investigate plausible relationships between similar reconfiguration graphs.

The reconfiguration graph C_k(G) for the k-colourings of a graph G has a vertex for each proper k-colouring of G, and two vertices of C_k(G) are adjacent precisely when those k-colourings differ on a single vertex of G. Much work has focused on bounding the maximum value of diamC_k(G) over all n-vertex graphs G. We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if L is a list-assignment for a graph G with |L(v)|≥d(v)+2 for all v∈V(G), then diamC_L(G)≤n(G)+μ(G). We also conjecture that if (L,H) is a correspondence cover for a graph G with |L(v)|≥d(v)+2 for all v∈V(G), then diamC_(L,H)(G)≤n(G)+τ(G). (Here μ(G) and τ(G) denote the matching number and vertex cover number of G.) For every graph G, we give constructions showing that both conjectures are best possible, which also hints towards an exact form of Cereceda's Conjecture for regular graphs. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) diamC_L(G)≤n(G)+2μ(G) and diamC_(L,H)(G)≤n(G)+2τ(G). Our second main result proves that both conjectured bounds hold, whenever all v satisfy |L(v)|≥2d(v)+1. We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree. The full paper can also be found at arxiv.org/abs/2204.07928.

We investigate the list packing number of a graph, the least k such that there are always k disjoint proper list-colourings whenever we have lists all of size k associated to the vertices. We are curious how the behaviour of the list packing number contrasts with that of the list chromatic number, particularly in the context of bounded degree graphs. The main question we pursue is whether every graph with maximum degree ∆ has list packing number at most ∆ + 1. Our results highlight the subtleties of list packing and the barriers to, for example, pursuing a Brooks’-type theorem for the list packing number.

List coloring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-coloring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a (Formula presented.) -list-assignment (Formula presented.) of a graph (Formula presented.), which is the assignment of a list (Formula presented.) of (Formula presented.) colors to each vertex (Formula presented.), we study the existence of (Formula presented.) pairwise-disjoint proper colorings of (Formula presented.) using colors from these lists. We may refer to this as a list-packing. Using a mix of combinatorial and probabilistic methods, we set out some basic upper bounds on the smallest (Formula presented.) for which such a list-packing is always guaranteed, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of (Formula presented.). (The reader might already find it interesting that such a minimal (Formula presented.) is well defined.) We also pursue a more focused study of the case when (Formula presented.) is a bipartite graph. Our results do not yet rule out the tantalising prospect that the minimal (Formula presented.) above is not too much larger than the list chromatic number. Our study has taken inspiration from study of the strong chromatic number, and we also explore generalizations of the problem above in the same spirit.