Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Optimally Reconfiguring List and Correspondence Colourings   The reconfiguration graph $\mathcal{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 $\mathcal{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 ${\rm{diam}}~\mathcal{C}_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)|\ge
d(v)+2$ for all $v\in V(G)$, then ${\rm{diam}}~\mathcal{C}_L(G)\le
n(G)+\mu(G)$. We also conjecture that if $(L,H)$ is a correspondence cover for
a graph $G$ with $|L(v)|\ge d(v)+2$ for all $v\in V(G)$, then
${\rm{diam}}~\mathcal{C}_{(L,H)}(G)\le n(G)+\tau(G)$. (Here $\mu(G)$ and
$\tau(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. Our first main result proves the upper bounds (for the list and
correspondence versions, respectively) ${\rm{diam}}~\mathcal{C}_L(G)\le
n(G)+2\mu(G)$ and ${\rm{diam}}~\mathcal{C}_{(L,H)}(G)\le n(G)+2\tau(G)$. Our
second main result proves that both conjectured bounds hold, whenever all $v$
satisfy $|L(v)|\ge 2d(v)+1$. We also prove more precise results when $G$ is a
tree. 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.

36
The categories of this paper are: cmp-lg
13
The categories of this paper are: quant-ph
28
The categories of this paper are: alg-geom
32
The categories of this paper are: atom-ph
23
The categories of this paper are: solv-int
37
The categories of this paper are: supr-con
6
The categories of this paper are: astro-ph
3
The categories of this paper are: physics
9
The categories of this paper are: nlin
18
The categories of this paper are: econ
0
The categories of this paper are: hep-ph
31
The categories of this paper are: ao-sci
15
The categories of this paper are: nucl-ex
22
The categories of this paper are: chao-dyn
19
The categories of this paper are: eess
12
The categories of this paper are: nucl-th