Print Email Facebook Twitter Optimally reconfiguring list and correspondence colourings Title Optimally reconfiguring list and correspondence colourings Author Cambie, Stijn (Radboud Universiteit Nijmegen; University of Warwick; Katholieke Universiteit Leuven) Cames van Batenburg, W.P.S. (TU Delft Discrete Mathematics and Optimization) Cranston, Daniel W. (Virginia Commonwealth University) Date 2024 Abstract 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. To reference this document use: http://resolver.tudelft.nl/uuid:6b600371-f799-449e-8f95-517ebaef978b DOI https://doi.org/10.1016/j.ejc.2023.103798 ISSN 0195-6698 Source European Journal of Combinatorics, 115 Part of collection Institutional Repository Document type journal article Rights © 2024 Stijn Cambie, W.P.S. Cames van Batenburg, Daniel W. Cranston Files PDF 1_s2.0_S0195669823001154_main.pdf 662.29 KB Close viewer /islandora/object/uuid:6b600371-f799-449e-8f95-517ebaef978b/datastream/OBJ/view