Proof. The first statement follows from Theorem 5 since $2=\chi (P_n) \le \chi _{\ell }^\star (P_n) \le 2 \delta ^\star (P_n)=2$ .

For cycles, we first prove $\chi _\ell ^\star (C_n)\ge 3$ . When $n$ is odd we have $\chi _{\ell }^\star (C_n) \ge \chi (C_n)=3$ . When $n$ is even, we give a $2$ -list-assignment $L$ of $C_n$ which does not admit an $L$ -packing. Let the lists of the consecutive vertices $v_1$ up to $v_n$ of the cycle be $L_1, L_2, \ldots, L_n$ with $L_i =\{1,2\}$ for $1 \le i \le n-2$ , $L_{n-1}=\{1,3\}$ and $L_{n}=\{2,3\}$ . To rule out an $L$ -packing, it is sufficient to observe that no proper $L$ -colouring $c$ can satisfy $c(v_1)=2$ . An $L$ -colouring $c$ with $c(v_1)=2$ must have $c(v_i)=2$ for every odd $i$ such that $1 \le i \le n-3$ , and $c(v_i)=1$ for every even $i$ with $1\le i \le n-2$ . Continuing the colouring, $c(v_{n-1})$ must be $3$ , and going backwards from $v_1$ we see that $c(v_n)$ must also be $3$ , so $c$ cannot be proper. As there does not exist a list-packing in this case, we have $\chi _{\ell }^\star (C_n)\ge 3$ . Alternatively, one can construct the cover $(\hat L,H)$ of $C_n$ using these lists and observe that it contains an odd cycle. Thus, the 2-fold list-cover has chromatic number strictly greater than $2$ .

Now we prove the upper bound, that for every list-assignment $L$ of $C_n$ with lists of size 3 there exists an $L$ -packing. If all lists are the same, this is clear since we can pick an arbitrary proper colouring and take two translates of that one. Then the remaining case involves adjacent vertices $u$ and $v$ such that $L(u) \ne L(v)$ , and hence $\lvert L(u) \cap L(v) \rvert \le 2$ . The hardest case to prove is when the intersection has size exactly $2$ . Without loss of generality, in this case we can take $L(u) =\{1,2,3\}$ and $L(v)=\{1,2,4\}$ . First, take an arbitrary $L$ -packing $\vec{c} = (c_1, c_2, c_3)$ of $C_n \setminus \{u,v\}$ (which is isomorphic to a path $P_{n-2}$ ), The worst case is that the neighbour $w$ of $u$ in $C_n\setminus \{u,v\}$ has the same list $L(w)=\{1,2,3\}$ as $u$ , because if this is not the case there will simply be more options for extending the $L$ -packing to $u$ . Then without loss of generality we can assume that $c$ gives $w$ the colours $(c_1(w),c_2(w),c_3(w))=(1,2,3)$ in order, and hence $\vec c(u) =(3,1,2)$ and $\vec c(u) = (2,3,1)$ are both valid extensions of $c$ to $u$ . Similarly, there will be at least two possible choices for the extension of $c$ to $v$ . We are done if out of the (at least) four possible extensions of $c$ to both $u$ and $v$ , one of them is valid on the edge $uv$ . It is easy to see that among all permutations of $\{1,2,4\}$ , only the choice $\vec c(v) = (2,1,4)$ would yield a situation in which case the extension to $u$ is impossible. So there is always a choice for $\vec c(v)$ such that the $L$ -packing can be completed.

Proof. The first statement is true since $2=\chi (P_n) \le \chi _{c}^\star (P_n) \le 2 \delta ^\star (P_n)=2$ . The upper bound $\chi _{c}^\star (C_n)\le 2 \delta ^\star (C_n)=4$ follows from Theorem 5 as well. It remains to give, for every $n\ge 3$ , a $3$ -fold correspondence-cover $\mathscr{H}=(L,H)$ of $C_n$ for which no $\mathscr{H}$ -packing exists.

Let $xy$ be an arbitrary edge of $C_n$ , and for each $v\in C_n$ , let $L(v)=\{1_v,2_v,3_v\}$ . Form the cover $H$ by connecting $i_u$ and $i_v$ for every edge $uv\in E(C_n)\setminus \{xy\}$ . Between $L(x)$ and $L(y)$ , we connect $2_x$ to $3_y$ and $3_x$ to $2_y$ , as well as $1_x$ to $1_y$ . This is presented for $C_4$ and $C_5$ in Fig. 1. Assume there is an $\mathscr{H}$ -packing, i.e. there is a vector $\vec c = (c_1,c_2,c_3)$ such that $c_i$ is an independent transversal with $c_i(v) \in L(v)$ , and such that $c_i(v) \ne c_j(v)$ for $i \ne j$ . For every $v$ , we have that $\vec c(v)=(c_1(v),c_2(v),c_3(v))$ is a permutation of $(1_v,2_v,3_v)$ . Furthermore, for any edge $uv$ other than $xy$ , when we drop the subscripts and consider $\vec c(u)$ and $\vec c(v)$ as permutations of $\{1,2,3\}$ , they do not have an index mapped to the same value. That is, $\vec c(v)\vec c(u)^{-1}$ is a derangement. In particular, $\vec c(v)\vec c(u)^{-1}$ is an even permutation because the only derangements of $\{1,2,3\}$ are the even permutations $(2,3,1)$ and $(3,1,2)$ . On the other hand, for the edge $xy$ we must have that $\vec c(x)\vec c(y)^{-1}$ is an odd permutation. This leads to a contradiction as follows. Permuting the labels if necessary, we may assume that $\vec c(x) = (1_{x}, 2_{x}, 3_{x})$ is the identity permutation. The above argument shows that going around the cycle in order, starting at $x$ and going away from $y$ , each $\vec c(v)$ must be an even permutation, including $\vec c(y)$ . We now have a contradiction as to prevent the packing from containing colourings that make $xy$ monochromatic, we must have that $\vec c(y)$ is an odd permutation.

Proof of Proposition 1 . A forest with at least one edge is $1$ -degenerate, so by Theorem 5 it has correspondence packing number at most $2$ . Since $\chi (K_2)=2$ , the list and correspondence packing number must in fact be exactly $2$ . Conversely, if a graph is not a forest then it contains a cycle which via Proposition 2 forces the list packing number to exceed $2$ .

Proof. It suffices to prove, for every graph $G$ with maximum degree $3$ and any $4$ -fold correspondence-cover $\mathscr{H}=(L,H)$ of $G$ , there exists a correspondence-packing. Clearly, it is sufficient to check all $4$ -fold correspondence-covers in which full matchings are taken between $L(u)$ and $L(v)$ for each edge $uv$ of $G$ . One only has to check connected graphs $G$ , and by Theorem 5 we only have to consider cubic graphs. Briefly, in the case that $G$ has a vertex $v$ with degree at most $2$ , one can extend a correspondence-packing on $G \setminus \{v\}$ by Hall’s marriage theorem as shown in the proof of Theorem 5 given as [Reference Cambie, van Batenburg, Davies and Kang5, Thm. 9].

For the complete graph $K_4$ , it is known that $\chi _{c}^\star (K_4)=4$ . This can be checked by brute force, as we have done with Sage,Footnote 1 and Yuster did in [Reference Yuster27, App. A].

Let $G=(V,E)$ be an arbitrary connected cubic graph on $n$ vertices such that $G$ is not $K_4$ . By the following claim, $G$ has an edge $uv$ which is not part of a triangle.

Using the claim, let $uv$ be an edge of $G$ not contained in a triangle, and let $\mathscr{H}=(L,H)$ be a $4$ -fold correspondence-cover of $G$ . We let $u_1$ , $u_2$ and $v_1$ , $v_2$ be the two neighbours of $u$ and $v$ respectively, different from $u$ and $v$ themselves. The vertices $X=\{u_1,u_2, v_1,v_2\}$ are distinct by the choice of the edge $uv$ . Since the edges $F=\{uu_1, uu_2, uv, vv_1, vv_2\}$ form a tree on $X$ , we can ‘untwist’ the (full) matchings in $H$ covering $F$ without loss of generality. That is, we can label $L(x)=\{1_x,2_x,3_x,4_x\}$ for each $x\in X$ such that for each $xy\in F$ , the matching in $H$ between $L(x)$ and $L(y)$ is the “identity” connecting $i_x$ to $i_y$ for $1\le i\le 4$ . Let $\vec{c} = (c_1, c_2, c_3, c_4)$ be a correspondence-packing for $G\setminus \{u,v,u_2,v_1,v_2\}$ , which exists by Theorem 5. We can assume without loss of generality that $\vec c(u_1)=(c_1(u_1),c_2(u_1),c_3(u_1),c_4(u_1))=(1_{u_1},2_{u_1},3_{u_1},4_{u_1})$ , and it is sufficient to prove that this packing $\vec c$ can be extended to a correspondence-packing for $G$ . We can drop the subscripts and consider the vectors $\vec c(x)$ , which we must define for $x\in X\setminus \{u_1\}$ , as permutations of $\{1,2,3,4\}$ .

Figure 2.

The local structure of $G$ . Note that there could be edges amongst $\{u_1,u_2,v_1,v_2\}$ which we do not attempt to picture.

Starting from $\vec{c}$ (the partial packing for $G\setminus \{u,v,u_2,v_1,v_2\}$ ), we now do the following.

1. 1. Choose a permutation $\vec c(u_2)$ different from $(2, 3, 4, 1)$ , $(2, 4, 1, 3)$ , $(3, 1, 4, 2)$ and $(4, 1, 2, 3)$ such that $\vec c$ is a proper packing of $G\setminus \{u, v, v_1,v_2\}$ . Using a computer, we show that this can be done for any possible placement of the edges of $G\setminus \{u, v, v_1,v_2\}$ and choices of matchings covering the edges incident to $u_2$ , using the fact that $u_2$ has at most two neighbours in $V\setminus \{u,v,v_1,v_2\}$ .

2. 2. Given the four special exclusions, there are 20 remaining permutations which $\vec c(u_2)$ could be. We show that these 20 choices can be partitioned as follows.

   1. (i) There are 10 ‘excellent’ choices, for which the packing can be greedily extended to $v_1$ , and then $v_2$ such that a valid choice of $(\vec c (u), \vec c (v))$ remains.

   2. (ii) There are 8 ‘good’ choices such that, provided exactly one problematic set $\{\vec c(v_1), \vec c(v_2)\}$ is avoided, a valid (at least one) choice of $(\vec c (u), \vec c (v) )$ remains. Avoiding one problematic set is always possible, since there are at least two available permutations when extending the partial packing to a vertex which has at most $2$ neighbours which are already coloured/packed.

   3. (iii) There are 2 ‘bad’ choices such that there are 8 further problematic sets $\{\vec c(v_1), \vec c(v_2)\}$ that must be avoided. In this case it is not immediate that choices avoiding these problematic sets are possible, but we verify that the packing can be completed nonetheless.

Having given the idea of the steps to extend the partial list-packing, we now give the details why it works. Using a computer programFootnote 2 we can list all possible choices (there are $112$ of them) for $(\vec c(u_2), \vec c(v_1), \vec c(v_2))$ for which the list-packing cannot be extended to both $u$ and $v$ , i.e. to a full proper list-packing of $G$ . In the code, this is marked by the comment “In [Reference Aharoni, Berger and Ziv1]”. Intuitively, since $112\ll (4!)^3$ , there are only few problematic choices for $(\vec c(u_2), \vec c(v_1), \vec c(v_2))$ and we can avoid these, as we show next.

No matter the colourings of the neighbours of $u_2$ different from $u$ , we can choose $\vec c(u_2)$ different from $(2, 3, 4, 1)$ , $(2, 4, 1, 3)$ , $(3, 1, 4, 2)$ and $(4, 1, 2, 3)$ . For this, we note that at most two neighbours of $u_2$ can be packed by $\vec c$ thus far. This is done at the comment “In [Reference Cambie4]” in the code. Going through the $112$ bad triples at “In [Reference Borodin3]”, one concludes that there are $6$ “bad” choices for $\vec c(u_2)$ belonging to $16$ non-extendable triples, and $8$ “good” possibilities for $\vec c(u_2)$ to $2$ non-extendable triples. In the latter case, there is only one set $\{\vec c(v_1), \vec c(v_2)\}$ for which the extension was impossible (since switching the two gives the same obstruction). In those cases one can always choose $\vec c(v_1)$ and $\vec c(v_2)$ such that they are not equal to such a bad set, since once the derangements of two neighbours of $v_2$ are chosen, there are at least two possible extensions for $v_2$ (see “In [Reference Alon, Fellows and Hare2]”). That is, in the good cases one can indeed complete the packing.

We can afford to reduce the $6$ “bad” cases to $2$ , as there is enough flexibility to take $\vec c(u_2)$ different from $4$ of the $6$ bad choices. That is, up front we choose $\vec c(u_2)$ different from the bad choices $(2, 3, 4, 1)$ , $(2, 4, 1, 3)$ , $(3, 1, 4, 2)$ and $(4, 1, 2, 3)$ . The remaining bad cases are when $\vec c(u_2)$ is equal to either $(3, 4, 2, 1)$ or $(4, 3, 1, 2)$ . But in these two last cases, one can extend the partial (correspondence) colourings to $v_1$ and $v_2$ , in such a way that $\vec c(v_1)$ and $\vec c(v_2)$ are not taken from the set $\{(1, 3, 2, 4), (3, 2, 1, 4), (4, 2, 3, 1), (1, 4, 3, 2)\}$ (see “In [Reference Cambie, van Batenburg, Davies and Kang5]”). For the latter, we verify at “In [Reference Cambie, Cames van Batenburg and Zhu.6]” that the triple of choices $(\vec c(u_2), \vec c(v_1), \vec c(v_2))$ does permit an extension of $\vec c$ to both $u$ and $v$ as required. As such, we conclude that we always can choose $\{\vec c(x) \mid x \in \{u_1,u_2,v_1,v_2\} \}$ such that the correspondence-packing can be extended to $u$ and $v$ as well, i.e. we have a correspondence-packing for $G$ .

Proof. Since the minimum degree is $m$ , every $A_1 \subseteq A$ with $\left |A_1\right | \le m$ satisfies $\lvert N(A_1) \rvert \ge \lvert A_1 \rvert$ . On the other hand, since all vertices in $B$ also have minimum degree $m$ , whenever $\lvert A_1 \rvert \ge m+2$ and thus $\lvert A \setminus A_1 \rvert \lt m$ , every vertex in $B$ has a neighbour in $A_1$ and thus $N(A_1)=B$ again has size $\geq \lvert A_1 \rvert$ . As such, the only exception is when $\lvert A_1 \rvert =m+1$ and $\lvert N(A_1)\rvert =m$ . In that case, denote $A_2=A \setminus A_1$ , $B_1=N(A_1)$ , and $B_2=B\setminus B_1$ . By the minimum degree condition and the definitions, we conclude that $G[A_1,B_2]$ is the empty graph and $G[A_1,B_1]$ and $G[A_2,B_2]$ are complete bipartite graphs. Examples are presented in Fig. 3, where blue dashed edges can be present or not.

Proof. Take an arbitrary subset $A_1 \subseteq A$ . If $\left |A_1\right | \le m-1$ , then due to the minimum degree condition $\delta (G)\ge m-1$ , it is immediate that $\lvert N(A_1) \rvert \ge m-1 \ge \lvert A_1 \rvert$ . In the case $\lvert A_1 \rvert \ge$ $m+2$ , and thus $\lvert A \setminus A_1 \rvert \lt m-1=\delta (G)$ , every vertex in $B$ has a neighbour in $A_1$ and thus $N(A_1)=B$ , so the condition in Theorem 12 again holds. As such, the condition can only not hold when $\left |A_1\right | \in \{m,m+1\}$ and $m-1 \le \left | N(A_1)\right |\le \left |A_1\right |-1$ . The partial characterisation of the extremal graphs is true by the minimum degree condition applied to $A_1,$ $A_1$ and $B_2,$ and $B_2$ respectively.

Proof of Theorem 6. We may assume that $G$ is connected. If $G$ is not $\Delta$ -regular, then $\delta ^\star (G) \le$ $\Delta -1$ , and the theorem is true by [Reference Cambie, van Batenburg, Davies and Kang5, Thm. 9]. So we may assume that $G$ is $\Delta$ -regular, for a fixed $\Delta \ge 4$ . Let $m=\Delta -1\ge 3$ , and $k=2m =2\Delta -2$ . Let $H$ be a $k$ -fold correspondence-cover of $G$ , via some correspondence-assignment $L\,:\,V(G) \to 2^{V(H)}$ . To be concrete, we label $L(v) = \{1_v, 2_v, \dotsc, k_v\}$ for each $v\in V(G)$ and we drop the subscripts where convenient. Take an arbitrary edge $uv$ of $G$ . Without loss of generality (one can rename the colours if necessary), we assume that the matching in $H$ between $L(u)$ and $L(v)$ is the “identity” connecting $i_u$ to $i_v$ for $1\le i\le k$ .

Let $\vec c$ be a correspondence-packing of $G\setminus \{u, v\}$ for the cover graph $H\setminus (L(u)\cup L(v))$ , which exists by the non-regular case of the theorem. It suffices to extend $\vec c$ to both $u$ and $v$ . We will do so by first choosing $\vec c(u)$ by imposing at most two additional constraints on the choice, and then $\vec c(v).$ For every $1\le i \le k$ , let $U_i = L(u)\setminus (\bigcup _{w \in N_G(u)\setminus \{v\}}N_H(c_i(w))$ , and define $V_i$ similarly. Note that the set $U_i$ collects all possible elements of $L(u)$ that can be used for $c_i(u)$ in a proper extension of $\vec{c}$ to $u$ and the same is true for $V_i$ . However, some choices of pairs $c_i(u) \in U_i$ and $c_i(v) \in V_i$ may still be in conflict so cannot be used simultaneously for an extension of $\vec{c}$ .

We first prove the following claim, that will be useful to show that a proper extension is possible.

Figure 5.

Sketch of claim 19, possible edges of $G$ .

Construct the bipartite graph $G_v$ whose bipartition is $A=(V_i)_{ 1\le i \le 2m}$ and $B=[k]$ and an edge between $V_i$ and $j \in [k]$ if and only $j_v \in V_i$ . Define the bipartite graph $G_u$ analogously. Since only $\Delta -1$ neighbours of $u$ are already packed, $G_u$ has minimum degree at least $2m-(\Delta -1) =m$ , so $G_u$ satisfies Hall’s marriage theorem, meaning that $G_u$ contains a perfect matching. This matching corresponds to a choice of $\vec{c}(u)$ which extends the packing $\vec{c}$ to $u$ . However, we want to make this choice in a slightly more intricate way, since afterwards we also need to extend $\vec{c}$ to $v$ . That is, we do not merely want to find a perfect matching in $G_v$ , but rather a perfect matching in $G_v \setminus M$ , for some matching $M$ determined by the choice of $\vec{u}$ .

If there does not exist a matching $M$ such that $G_v \setminus M$ does not satisfy Hall’s marriage theorem, then one can choose $\vec{c}(u)$ and then $\vec{c}(v)$ by assumption, since the latter corresponds to finding a matching in $G_v \setminus M$ for some matching $M$ that is determined by $\vec{c}(u)$ .

If there exists a matching $M$ such that $G_v \setminus M$ does not satisfy Hall’s marriage theorem, then $G_v\setminus M$ is a bipartite graph with minimum degree $m-1$ for which one of the three cases in Lemma 18 is satisfied. Up to renaming $A$ and $B$ , in all three cases there are partitions $A=A_1 \cup A_2$ and $B=B_1 \cup B_2$ satisfying the conditions of Claim 19. Choose two specific edges of $G_v[A_1,B_2]$ (which is a matching $mK_2+K_1$ ), which correspond with pairs $(V_i, x_v), (V_j, y_v)$ . We can impose two additional constraints on the choice for $\vec{c}(u)$ ; $c_i(u) \not = x_u$ and $c_j(u) \not = y_u$ for some $x_u, y_u \in [k]$ and indices $1 \le i\lt j \le k$ . These constraints can be implemented by taking $U^{\prime}_i=U_i \setminus x$ and $U^{\prime}_j=U_j \setminus y$ and $U^{\prime}_{\ell }=U_\ell$ for the remaining indices in $[k]$ . Equivalently, we have deleted the edges $e_1=(U_i, x)$ and $e_2=(U_j, y)$ of $G_u$ . This implies that in both partition classes of $G_u$ , at most $2$ vertices have degree equal to $m-1$ . Since in each of the three bad cases in Lemma 18 there are at least $m\ge 3$ vertices in one partition class whose degree is $m-1$ , we conclude that $G_u$ always contains a perfect matching. That is, one can choose $\vec{c}(u)$ with $c_i(u) \in U^{\prime}_i$ being distinct for every $1 \le i \le k$ . By definition of the $U_i$ , this is an extension of the partial packing. Once $\vec{c}(u)$ has been chosen like this, one can apply Hall’s theorem again on $V^{\prime}_i= V_i \backslash N(c_i(u)), 1 \le i \le k$ to find $\vec{c}(v)$ . The edges $(V_i, N(c_i(u))\cap L(v))$ for $i \in [k]$ form a matching $M$ for which $G_v\backslash M$ has a perfect matching by Claim 19. The latter perfect matching corresponds with a choice of $\vec{c}(v)$ that extends the partial packing to a correspondence-packing $\vec{c}$ on $G$ .

Proof of Theorem 4. For $\Delta =1$ , the bounds follow from Theorem 5. For $\Delta \in \{2,3\}$ we need Theorems 13, 14, and 15. Finally, Theorem 6 gives the upper bound of $\chi _c^\star (G)\le 6$ when $\Delta =4$ . All of these bounds are sharp due to the complete graph $K_{\Delta +1}$ .

Proof. By adding edges to the cover $H$ if necessary, we may assume that for every edge $uv$ of $G$ , the matching between $L(u)$ and $L(v)$ is maximum, i.e. of size $\min \{|L(u)|, |L(v)|\}$ . We proceed by induction on the number of vertices of $G$ . The base case $G = \varnothing$ holds vacuously.

For the induction step, we take a vertex $v$ of $G$ whose list $L(v)$ has maximum size among all vertices of $G$ . Pick a uniformly random vertex $x \in L(v)$ . By induction, there exists a random independent set $I_x$ in $H-N[x]$ which satisfies the lemma with respect to the reduced lists $(L(w)-N[x])_{w\in V(G)}$ obtained after removing $N[x]$ . Note that $H-N[x]$ is a valid correspondence-cover for $G-v$ via the map $L$ such that the list of each vertex is large enough, as any list which decreased in size decreased in size by exactly $1$ , but the vertices whose lists decreased in size lost the neighbour $v$ . That is, the conditions are satisfied because $|L(w)-N[x]|\geq |L(w)|-1 \geq \deg (w) = \deg _{G-v}(w)+1$ for every neighbour $w$ of $v$ , while still $|L(w)-N[x]|=|L(w)|\geq \deg (w)+1=\deg _{G-v}(w)+1$ for every non-neighbour $w$ of $v$ .

The union of $x$ and $I_x$ is the claimed random independent set $I$ . Let us confirm this for three types of vertices:

• • For every $y \in L(v)$ , we have $\mathop{\mathbb{P}}\nolimits ( y \in I) = \mathop{\mathbb{P}}\nolimits ( y =x) = 1/ |L(v)|$ , by definition.

• • If $u \in V(G)- N[v]$ and $y \in L(u)$ , then $\mathop{\mathbb{P}}\nolimits (y \in I) \geq 1/ |L(u)|$ is immediate, as this inequality holds conditioned on any choice of $x$ .

• • Finally, let $u\in N(v)$ and let $y\in L(u)$ . Note that then $|L(u)| \geq \deg (u)+1 \geq 2$ . We consider three cases for $x$ : either it is adjacent to $y$ itself, it is adjacent to a colour in $L(u)\setminus \{y\}$ , or it has no neighbours in $L(u)$ . If $x\sim y$ then $y$ cannot be in $I$ . If $x$ is adjacent to a colour in $L(u)\setminus \{y\}$ then $y$ is in $I_x$ and hence $I$ with probability at least $1/(|L(u)|-1)$ , and in the case that $x$ has no neighbours in $L(u)$ , the probability that $y$ is in $I$ is $1/|L(u)|$ . Since the matching between $L(u)$ and $L(v)$ is maximum by assumption, and $L(v)$ is a list of maximum size, we have $|L(v) - N(L(u))|=|L(v)|-|L(u)|$ . This means that the probability of the third case satisfies

  \begin{equation*} \mathop {\mathbb {P}}\nolimits (x \notin N(L(u))) = \frac {|L(v)|-|L(u)|}{|L(v)|}, \end{equation*}
  which is not too big. Putting the conditional probabilities together, we conclude that
  \begin{align*} \mathop{\mathbb{P}}\nolimits (y \in I) &= \frac{1}{|L(u)|-1}\mathop{\mathbb{P}}\nolimits (x \in N(L(u)-y)) + \frac{1}{|L(u)|}\mathop{\mathbb{P}}\nolimits (x \notin N(L(u))) \\ &\ge \frac{1}{|L(u)|-1} \cdot \frac{|L(u)|-1}{|L(v)|} + \frac{1}{|L(u)|} \cdot \frac{|L(v)|-|L(u)|}{|L(v)|}\\ &= \frac{1}{|L(u)|}. \end{align*}

As such, we have proved the required lower bound on $\mathop{\mathbb{P}}\nolimits (y\in I)$ for every vertex of $H$ , as required.

We remark that after submission of this manuscript, the proof method of Lemma 20 has been further developed in [Reference Cambie, Cames van Batenburg and Zhu.6, Lemma 7.3] and its applications.

Proof. We will iteratively construct a graph $G$ with $\delta ^\star (G)=d$ and a $(d+1)$ -list-assignment $L$ such that the covergraph $H$ satisfies $\chi _f(H)\gt d+1$ , implying $\chi _\ell ^\bullet (G)\ge d+2$ . We will do so by constructing a sequence of subgraphs $G_1,G_2,\ldots, G$ such that $V(G_1) \subset V(G_2) \subset \ldots \subset V(G)$ .

We start by choosing $G_{1}=(V_1,E_1)=K_{d+1}$ and the associated lists being equal to $[d+1]$ for all vertices. We now construct $G_2$ by adding a copy $v^{\prime}$ for every $v \in V_1$ that is connected to all vertices in $V_1 \setminus v$ . Let $V_2=V(G_2) \setminus V_1$ and $L(v^{\prime})=([d+1]\setminus \{1\}) \cup \{d+2\}$ for every $v^{\prime}\in V_2$ . Repeating this procedure, in step $m$ we add copies $v^{\prime}$ for every $v \in V_m$ and connect it to all vertices in $V_m \setminus \{v\}$ and call the set of added vertices $V_{m+1}$ . For $v^{\prime} \in V_{m+1}$ , we let $L(v^{\prime})=\mathrm{s}_{ij}(L(v))=(L(v) \setminus \{i\} )\cup \{j\}$ for some $i,j \in [d+2]$ , i.e. an $(i,j)$ -shift is applied to the lists. Here we set $V_m=\{v_1^m,\ldots, v_{d+1}^m\}$ , where $v_i^{m+1}$ denotes the copy of $v_i^m$ . We choose the shifts to be $\mathrm{s}_{1,d+2},\mathrm{s}_{2,1},\mathrm{s}_{d+2,2}$ in the first three steps. In general, with a transposition $(i\ j)$ we associate the shifts $\mathrm{s}_{i,d+2},\mathrm{s}_{j,i},\mathrm{s}_{d+2,j}$ .

Figure 6.

The construction of Proposition 21 for $d=2$ .

We repeat the procedure and form the permutation $(d, 1,2,3,\ldots, d-1)$ by applying the associated transpositions corresponding to $(1\, 2),(1\, 3),\dotsc,(1\, d)$ in order. Now continue doing the exact same $3(d-1)$ transpositions another $d-2$ times. Finally, add a vertex $w$ and connect it to $v_1^{3p(d-1)+1}$ for every $0 \le p \le d-1$ , and let $L(w)=[d+1]$ as well. In all steps, we connected new vertices to exactly $d$ existing vertices and so the degeneracy of the construction satisfies $\delta ^{\star }(G)=d$ . Fig. 6 gives the construction for $d=2$ .

We now analyse the construction, proving the claimed lower bound on the fractional chromatic number. The plausible $L$ -colourings of $G[V_1]$ give a permutation of $[d+1]$ . Fix such a colouring of $V_1$ and consider it a partial $L$ -colouring of $G$ . There is one vertex in $V_2$ whose neighbours in $V_1$ are coloured with $[d+1]\setminus \{1\}$ and hence has to be coloured with $d+2$ . The other vertices in $V_2$ have two possible colours, $d+2$ and some $i \in [d+1]\setminus \{1\}$ .

A fractional $L$ -packing of $G$ is a fractional colouring of weight $d+1$ of the cover graph of $G$ associated with $L$ , which corresponds to a random $L$ -colouring $c$ of $G$ such that for each vertex $v$ of $G$ and every $x\in L(v)$ , $\mathop{\mathbb{P}}\nolimits (c(v)=x)=1/(d+1)$ . Since $L$ gives each vertex in $V_2$ the same list, for each colour $x\ne d+2$ , the expected number of vertices in $V_2$ with $c(v)=x$ is at least $1$ , and hence the expected number of vertices in $V_2$ which do not get colour $d+2$ is at least $d$ . This means that the expected number of vertices in $V_2$ which get colour $d+2$ is at most $1$ . Since every $L$ -colouring of $G$ has at least one vertex in $V_2$ coloured with $d+2$ , we conclude that in fact every $L$ -colouring in the fractional packing (i.e. which occurs with positive probability) gives exactly one vertex in $V_2$ the colour $d+2$ . This implies that for every colouring in the fractional packing, the colouring restricted to $V_1$ implies the colouring of $V_2$ . More specifically, $c(v_i^2)=c(v_i^1)$ if $c(v_i^1)\not =1$ and $c(v_i^2)=d+2$ if $c(v_i^1)=1$ , or equivalently $c(v_i^2)=s_{1,d+2}c(v_i^1)$ for every $i \in [d+1]$ . Furthermore, this observation goes through when comparing partial $L$ -colourings of $V_m$ and $V_{m-1}$ . As such, for any colouring $c$ in the fractional packing, $c\left (v_i^{3p(d-1)+1}\right )$ for $0 \le p \le d-1$ either contains all colours in $[d]$ or all of them are equal to $d+1$ . From this, we can conclude that $c(w)=d+1$ or $c(w) \in [d]$ , respectively, i.e. $c(v_1^1)=d+1 \Leftrightarrow c(w)\ne d+1$ . The latter implies that the colour $d+1$ appears once on $\{v_1^1,w\}$ , while on average it should appear $\frac{2}{d+1}$ times on these two vertices. Since $d \geqslant 2$ , this is a contradiction. Hence no fractional $L$ -packing exists and thus $\chi _{\ell }^\bullet (G)\gt d+1$ .

Proof. Consider a correspondence-cover $(L,H)$ of $G$ such that for all vertices $v$ of $G$ , $|L(v)|=\Delta _A+1$ . It is sufficient to prove the statement under the assumption that every matching in the correspondence-cover is a perfect matching. To bound the fractional chromatic number of $H$ , we construct a random (maximum) independent set $I=I_B \cup I_A$ of $H$ as follows. Let $I_B$ contain for each vertex $b\in B$ a uniform random colour $x_b\in L(b)$ , chosen independently. Having fixed a choice of $I_B$ , we now choose $I_A$ . Each vertex $a\in A$ has at most $\Delta _A= k-1$ neighbours in $B$ , so at least one colour in $L(a)$ is non-adjacent to $I_B$ . Then we may choose a uniformly random colour $x_a$ from $L(a)\setminus N(I_b)$ , and include it in $I_A$ .

Note that for any $a\in A$ , the subgraph of $H$ induced by $L(a)$ and $\bigcup _{b \in N(a)}L(b)$ is isomorphic to the cartesian product of a complete graph $K_k$ and a star with $|N(a)|$ leaves. By the symmetry of this graph and how $I_b$ is chosen at random, for each $a\in A$ every $x_a\in L(a)$ is in $I$ with the same probability. Since the size of the intersection $|I_A\cap L(a)|$ is always exactly $1$ , taking expectations we have $\mathop{\mathbb{P}}\nolimits (x_a\in I)=1/k$ for all $a\in A$ and $x_a\in L(a)$ . We conclude that each vertex of $H$ is in $I$ with probability exactly $\frac 1k$ , so $\chi _f(H) \le k = \Delta _A+1$ .

Proof of Proposition 10. We give examples for each case that the quantities can be different.

• • Every even cycle $C_{2n}$ satisfies

  \begin{equation*} \chi _\ell (C_{2n})=2\lt 3=\chi _\ell ^\bullet (C_{2n})=\chi _\ell ^\star (C_{2n}). \end{equation*}
  The list chromatic number of even cycles has been known since the initial study [Reference Erdős, Rubin and Taylor10]. By Theorem 13, $\chi _\ell ^\star (C_{2n})=3$ . Moreover, the 2-fold cover of $C_{2n}$ via the list-assignment given in the proof of Theorem 13 contains an odd cycle and hence has fractional chromatic number strictly greater than $2$ ; this proves $3\leq \chi _\ell ^\bullet (C_{2n})$ .

• • The fan $F_7$ (formed by adding a universal vertex to a path on 6 vertices) satisfies

  \begin{equation*} \chi _\ell (F_7)=\chi _\ell ^\bullet (F_7)=3\lt 4=\chi _\ell ^\star (F_7). \end{equation*}
  Note that $K_3$ is a subgraph of $F_7$ to conclude that $3 \le \chi _\ell (F_7)\le \chi _\ell ^\bullet (F_7)$ . A brute-force verificationFootnote 3 shows that $\chi _c^\bullet (F_7)=3$ , which gives the upper bound $\chi _\ell ^\bullet (F_7)\le 3$ .

  A list-assignment and verification indicating that $\chi _{\ell }^\star (F_7)\ge 4$ is presented in [Reference Cambie4, Fig. 11.1, Tab. 11.1].

• • The complete bipartite graph $K_{3,3}$ is an example for which

  \begin{equation*} \chi _c(K_{3,3})=3\lt 4=\chi _c^\bullet (K_{3,3})=\chi _c^\star (K_{3,3}). \end{equation*}
  Note that $3=\chi _c(C_4)\le \chi _c(K_{3,3})\le 3$ , where the last inequality is true since at most $3\cdot 3!=18$ out of $27$ possible colourings of one partition class cannot be extended to the other partition class (it also follows from Brooks’ theorem for correspondence colouring). The inequality $3\lt \chi _c^\bullet (K_{3,3})$ is proved by computer verificationFootnote 4 and the upper bound $\chi _c^\star (K_{3,3}) \le 4$ is given in Theorem 15.

• • Any cycle $C_n$ satisfies

  \begin{equation*} \chi _c(C_n)=\chi _c^\bullet (C_n)=3\lt 4=\chi _c^\star (C_n). \end{equation*}
  The equality $\chi _c(C_n)=3$ was observed by Dvořák and Postle in [Reference Dvořák and Postle9]. The equality $\chi _c^\bullet (C_n)=3$ follows from Theorem 7. The equality $\chi _c^\star (C_n)=4$ is from Theorem 14.