List packing number of bounded degree graphs

Abstract

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 $\Delta$ has list packing number at most $\Delta +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.

1. Introduction

List colouring is a well-known generalisation of graph colouring in which we wish to find a proper colouring of a graph, but an adversary supplies a list of colours for each vertex and we must choose a colour for each vertex from its list. The importance of this notion is its flexible role in inductive approaches, such as, for example, iterative random colouring procedures [23]. Although there is already a rich collection of prominent challenges in list colouring (which relate well to algebraic, probabilistic, extremal, structural topics in graph theory), here we have set ourselves an even more difficult task of juggling multiple list-colourings simultaneously. We initiated the study of this topic in [5].

Formally, a list-assignment $L$ of a graph $G$ is a function $L\,:\,V(G)\to 2^{\mathbb{N}}$ , and an $L$ -colouring of $G$ is a colouring $c \colon V(G)\to \mathbb{N}$ such that for every vertex $v$ , $c(v)\in L(v)$ . As is standard, the $L$ -colourings we consider in this work are usually assumed to be proper, that is, $c(v)\ne c(v^{\prime})$ for any edge $vv^{\prime}$ . We call a list-assignment with $|L(v)|=k$ for all $v$ a $k$ -list-assignment. Recall that the list chromatic number of $G$ , denoted $\chi _\ell (G)$ , is the smallest $k$ such that for every $k$ -list-assignment $L$ , $G$ admits an $L$ -colouring. Our work is motivated by the idea to look for multiple, disjoint list-colourings. In particular, given a $k$ -list-assignment $L$ of $G$ we call a collection of $k$ pairwise-disjoint $L$ -colourings an $L$ -packing of size $k$ , or less specifically a list-packing. The list packing number $\chi ^\star _\ell (G)$ of $G$ is the least $k$ such that $G$ admits an $L$ -packing of size $k$ for any $k$ -list-assignment $L$ of $G$ . Clearly, $\chi ^\star _\ell (G)\ge \chi _\ell (G)$ always, and note how this implies the existence of a list-packing for any $k$ -list-assignment $L$ where $k\ge \chi ^\star _\ell (G)$ (by iteratively extracting $L$ -colourings).

The definitions above can easily be extended to a more general setup known as correspondence colouring. We defer the details of this more technical concept, as here it suffices to understand that replacing the notion of list colouring with correspondence colouring in the definitions above yields correspondence packing and the correspondence packing number we denote $\chi _c^\star (G)$ . It holds that $\chi ^\star _c(G) \ge \chi ^\star _\ell (G)$ always.

The list packing number is in a natural progression from the list chromatic number, in a similar way to how the chromatic number relates to the independence number; we remark more on this in Subsection 1.1. Indeed, list and correspondence packing were anticipated in earlier works—see, e.g. [2,8,19,21,27] – and it is thus surprising that our earlier work [5] was the first to systematically explore the notion, pointing to its potential throughout the landscape of (chromatic) graph theory. In our previous paper [5], we pursued amongst other things packing versions of list and correspondence chromatic number bounds in terms of the number of vertices or degeneracy of the underlying graph.

Considering the often deep relationship between the chromatic number and the independence number, the question directly comes to mind: truly how much “worse” is list packing in comparison to list colouring? In one interpretation of this question, what we audaciously named the List Packing Conjecture in [5], we proposed the list packing number might always be within some fixed constant factor of the list chromatic number. This mystery continues to fascinate us.

Although there are many tempting directions, more of which we mention further on, here we have restricted our attention to two of the most basic settings. We characterised graphs of list or correspondence packing number $2$ . And we have made progress for bounded degree graphs, especially for those of small degree. In this study, an approximate form of the packing numbers has naturally arisen. These settings have helped us uncover some interesting differences between finding a single list-colouring and a full packing of them and have served as proving ground for more general intuition.

The early, essential work of Erdős, Rubin and Taylor on list colouring [10] gives compass for results we may pursue for list and correspondence packing. In particular, Erdős, Rubin and Taylor characterised the graphs of list chromatic number $2$ using the so-called theta graphs. Here we obtain a characterisation for packing and find that the corresponding graph class is naturally, smaller and simpler.

Proposition 1. A graph $G$ has list packing number 2 if and only if it is a forest with at least one edge. The same holds for correspondence packing number.

Based on this, the next graphs to consider are of course cycles. We denote by $C_n$ a cycle on $n$ vertices. Here we find that there is no dependence on parity of $n$ , unlike for the respective colouring definitions.

Proposition 2. $\chi _\ell ^\star (C_n)=3$ and $\chi _c^\star (C_n) = 4$ .

These results give basis for the more difficult problem of list and correspondence packing in graphs of bounded maximum degree. Before discussing our results in this setting, we present a conjecture which should serve as a focal point for future study. These are prospective upper bounds for the list and correspondence packing numbers in terms of the maximum degree $\Delta (G)$ of a graph $G$ .

Conjecture 3. For any graph $G$ ,

1. (i) $\chi _{\ell }^\star (G) \le \Delta (G) +1$ ; and

2. (ii) $\chi _{c}^\star (G) \le 2 \left \lceil \frac{\Delta (G)+1}{2} \right \rceil$ .

Either bound would be sharp for every choice of $\Delta (G)\ge 2$ by considering the complete graph. For this, note that $\chi _{c}^\star (K_n) \ge \chi _{\ell }^\star (K_n) =n = \Delta (K_n)+1$ (the first equality was proved in [5]) and a construction of Catlin [8] (see e.g. [27]) shows that $\chi ^\star _c(K_n) = n+1=\Delta (K_n)+2$ if $n\ge 3$ is odd. In [5], we showed bounds within about a factor $2$ of the conjectured bounds (though we slightly improve on that earlier result below). In the special case of $K_n$ , Yuster [27] proved a bound within a factor $1.78$ for all sufficiently large $n$ . We note that Conjecture 3 is a broad generalisation of Conjecture 1.1 in [27], which in turn is related to the so-called “modified Fischer’s conjecture” (see [19]).

As evidence towards our conjecture, we have completely resolved a few of the first cases.

Theorem 4.

1. (i) Conjecture  3 ( i ) holds for $\Delta (G) \le 3$ .

2. (ii) Conjecture  3 ( ii ) holds for $\Delta (G) \le 4$ .

We remark that this last case implies that $\chi _c^\star (K_5)=6$ , which is a small step towards Conjecture 1.1 in [27]. It also implies some natural subcases for the so-called Strong Colouring Conjecture (see [1]). Partly with computer assistance, we establish Theorem 4 in separate pieces; namely, it follows by combining Theorems 13–15, and 6 below.

As alluded to, we previously [5] established a bound about twice the conjectured optimal. In fact, we proved the following upper bound in terms of the degeneracy $\delta ^\star (G)$ of $G$ .

Theorem 5 ([5, Thms. 3 and 9, Prop. 24]). For any graph $G$ , $\chi _\ell ^\star (G) \le \chi _c^\star (G) \le 2\delta ^\star (G)$ . The second inequality can be tight.

This implies an upper bound of $2\Delta (G)$ . It has proven frustratingly difficult to significantly improve on this in general. While the following result gives an improvement that is modest, particularly for large $\Delta (G)$ , we note the bound is best possible for $\Delta (G)=4$ (see Theorem 4 (ii) above) in the case of correspondence packing.

Theorem 6. For any graph $G$ with $\Delta (G) \ge 4$ , $\chi ^\star _\ell (G) \leq \chi ^\star _c(G) \leq 2\Delta (G)-2.$

For larger $\Delta (G)$ , although the above bound is still around a factor $2$ larger than we conjectured, it turns out that we can still find reasonable support for Conjecture 3 when we consider a mild relaxation of the list and correspondence packing numbers. We later give more formal definitions of the fractional list packing number $\chi _\ell ^\bullet (G)$ and the fractional correspondence packing number $\chi _c^\bullet (G)$ of $G$ . They are derived naturally from the idea that instead of integral packing, we could allow fractional weightings of the list- or correspondence-colourings of $G$ . The following thus constitutes the confirmation of a fractional relaxation of Conjecture 3.

Theorem 7. For any graph $G$ , $\chi _\ell ^\bullet (G)\le \chi _c^\bullet (G) \le \Delta (G)+1$ .

These fractional parameters may be of interest in their own right. Here and in Subsection 1.1 we discuss some of their basic properties in comparison to their integral counterparts. The following fractional form of our List Packing Conjecture as well as its correspondence analogue are worth further study.

Conjecture 8.

1. (i) There exists $C\gt 0$ such that $\chi _\ell ^\bullet (G) \leq C \cdot \chi _{\ell }(G)$ for any graph $G$ .

2. (ii) There exists $C\gt 0$ such that $\chi _c^\bullet (G) \leq C \cdot \chi _c(G)$ for any graph $G$ .

A challenge of dealing with list packing is how we must confront our usual intuition from colouring. In treating the fractional relaxation, we hoped to claw back some of that intuition, which we succeeded in doing in part in Theorem 7. Here are some obstacles and subtleties we must further account for.

Theorem 9.

1. (i) For each $d\ge 2$ , there is a graph $G$ satisfying $\delta ^\star (G)=d$ and $\chi _\ell ^\bullet (G) \ge d+2$ .

2. (ii) For each $k\ge 2$ , there is a graph $G$ satisfying $\chi _c^\bullet (G) = k+1$ and $\chi _c^\star (G) = 2k$ .

3. (iii) There is a connected $3$ -regular graph $G \ne K_4$ such that $ \chi _\ell ^\bullet (G) = 4$ .

Theorem 9(i) shows it impossible to improve Theorem 7 by replacing maximum degree by degeneracy, while Theorem 9(iii) shows how even a fractional relaxation of a list packing analogue must differ from the usual Brooks’ theorem. We prove items (i) and (ii) in Section 5, and item (iii) in Subsection 6.2.

Let us remark as an aside that, for many of the results we pursued with respect to Brooks’ theorem in the context of (fractional) list and correspondence packing numbers, they could also be pursued in the considerably more general setting of bounded maximum degree in the so-called cover graph, also referred to as bounded colour-degree. We have indeed already made a conjecture to this end [5, Conj. 13]; however, the problem without the extra complication of packing is already not so easily amenable to a Brooks’-type characterisation, which is why we have left this to future investigation.

We conclude this introductory section by confronting yet another tempting intuition. Isn’t it easy to construct a list-packing once we have sufficiently many list-colourings? In Subsection 6.1, we show how this line of thought needs something extra. For every integer $n\geq 2$ , we exhibit a graph $G$ on $n^2$ vertices together with an $n$ -list-assignment $L$ such that $G$ has

• • list chromatic number $n$ ,

• • $n^{n^2}$ not-necessarily-proper $L$ -colourings, and

• • $n^{n^2(1+o(1))}$ proper $L$ -colourings,

and yet it does not admit an $L$ -packing.

1.1 Notation, definitions, preliminaries

The reader will have noticed that we use a variety of standard graph theoretic notation including $\Delta (G)$ for the maximum degree, $\omega (G)$ for the clique number, $\delta ^\star (G)$ for the degeneracy, and $\chi (G)$ for the chromatic number of a graph $G$ .

Here now are some of the more formal notation and definitions most directly related to our list packing parameters. Let $G$ and $H$ be graphs. A pair $\mathscr{H}=(L,H)$ is a correspondence-cover of a graph $G$ if the graph $H$ and mapping $L\,:\,V(G)\to 2^{V(H)}$ satisfy that

1. (i) $L$ induces a partition of $V(H)$ ,

2. (ii) the bipartite subgraph of $H$ induced between $L(u)$ and $L(v)$ is empty whenever $uv\notin E(G)$ ,

3. (iii) the bipartite subgraph of $H$ induced between $L(u)$ and $L(v)$ is a matching whenever $uv\in E(G)$ ,

4. (iv) the subgraph of $H$ induced by $L(v)$ is a clique for each $v\in V(G)$ .

It can be convenient to drop $\mathscr{H}$ and $L$ from the notation, saying for example that some property of the correspondence-cover holds if it holds for $H$ as a graph. A correspondence-cover is $k$ -fold if $|L(v)|=k$ for each vertex $v$ of $G$ .

Note that a list-assignment $L$ of $G$ naturally gives rise to a correspondence-cover $(\tilde L, H)$ of $G$ by setting $\tilde L(v) = x_v$ for each $x\in L(v)$ , and forming $H$ on these vertices by putting in the necessary cliques and adding edges of the form $x_ux_v$ for each colour $x\in \bigcup _{v\in V(G)}L(v)$ and edge $uv\in E(G)$ . We call a correspondence-cover that arises from a list-assignment in this way a list-cover of $G$ .

We remark that in the literature, the concept of a cover is more general than a correspondence-cover, namely by the omission of condition 3. Moreover, it can be defined in various ways, where in particular the cliques on the lists can be omitted. In this paper, we embrace the inclusion of these cliques for convenience. In this way, the definition of list packing number $\chi _\ell ^\star (G)$ given above is equivalent to the least $k$ such that for every $k$ -list-assignment $L$ , the associated cover $(\tilde L, H)$ has chromatic number $k$ . Under this equivalence, each colour class in a proper $k$ -colouring of $H$ is precisely an $L$ -colouring of $G$ .

It is now straightforward to define correspondence colouring and packing. Given a correspondence-cover $\mathscr{H}=(L,H)$ of a graph $G$ , we say that an $\mathscr{H}$ -colouring of $G$ is an independent set of size $|V(G)|$ in $H$ and an $\mathscr{H}$ -packing of $G$ of size $k$ is a partition of $H$ into $k$ $\mathscr{H}$ -colourings of $G$ . The correspondence chromatic number $\chi _c(G)$ of $G$ is the least $k$ such that every $k$ -fold correspondence-cover $\mathscr{H}$ of $G$ has an independent set of size $|V(G)|$ . Similarly, the correspondence packing number $\chi _c^\star (G)$ is the least $k$ such that every $k$ -fold correspondence-cover $\mathscr{H}$ of $G$ has chromatic number $k$ (i.e. every $k$ -fold correspondence-cover $\mathscr{H}$ of $G$ admits an $\mathscr{H}$ -packing).

One can interpret a list- or correspondence-packing of $G$ (of size $k$ ) as an assignment of $\{0,1\}$ -weights to every possible independent set of size $|V(G)|$ in the corresponding cover of $G$ such that each cover vertex is assigned weight exactly once by some independent set containing it (and exactly $k$ independent sets are assigned nonzero weight). Then, as is common in combinatorics and optimisation, one can naturally “fractionally” relax the constraint that the weights be integral (so they may take values in the interval $[0,1]$ ), while demanding that the total weight assigned to a cover vertex is $1$ (and that the sum of the weights of the independent sets is exactly $k$ ). We find it particularly interesting to consider fractional relaxations of the packing numbers in our investigation of whether known results for $\chi _\ell$ and $\chi _c$ extend to the packing variants $\chi _\ell ^\star$ and $\chi _c^\star$ . The fractional list packing number of $G$ , denoted $\chi _\ell ^\bullet (G)$ , is the least integer $k$ such that every $k$ -fold list-cover of $G$ has fractional chromatic number $k$ . Similarly, the fractional correspondence packing number of $G$ , denoted $\chi _c^\bullet (G)$ , is the least integer $k$ such that every $k$ -fold correspondence-cover of $G$ has fractional chromatic number $k$ .

Note that the fractional packing numbers can only take on integer values; their fractional character lies in the manner in which weights may be distributed over the independent sets, but is not reflected in the sum of the weights. We remark that there are other viable notions of fractional packing numbers, but we found it most natural to introduce the above.

Since every list-cover is a correspondence-cover we have

\begin{align*} \chi _{\ell }(G) &\leq \chi _c(G),& \chi _{\ell }^{\bullet }(G) &\leq \chi _c^{\bullet }(G),&\chi _{\ell }^{\star }(G) &\leq \chi _c^{\star }(G); \end{align*}

and since the fractional chromatic number is a lower bound for chromatic number, the following inequalities also immediately follow from the above definitions:

\begin{align*} \chi _{\ell }(G) &\leq \chi _{\ell }^{\bullet }(G) \leq \chi _{\ell }^{\star }(G),& \chi _c(G) &\leq \chi _{c}^{\bullet }(G) \leq \chi _c^{\star }(G). \end{align*}

We prove at the end of Section 5 that these last inequalities can be strict.

Proposition 10. For each of the following four inequalities, there is some graph $G$ satisfying it:

\begin{align*} \chi _\ell (G)&\lt \chi _\ell ^\bullet (G),& \chi _\ell ^\bullet (G)&\lt \chi _\ell ^\star (G),& \chi _c(G)&\lt \chi _c^\bullet (G),& \chi _c^\bullet (G)&\lt \chi _c^\star (G). \end{align*}

The next result shows that a fractional packing is a stronger notion than the existence of a colouring extending every possible assignment of a colour to a vertex, and that fractional packings must be probability distributions over full list-colourings of the graph, i.e. they cannot assign positive weight to non-maximum independent sets in the cover graph.

Proposition 11. Let $G$ be a graph and $k\ge \chi _\ell ^\bullet (G)$ . Then for any $k$ -list-assignment $L$ of $G$ , for any $v\in V(G)$ and $x\in L(v)$ , there is a proper $L$ -colouring $c$ of $G$ with $c(v)=x$ .

Similarly, for any $k$ -fold list-cover $H$ of $G$ and fractional colouring $c$ of $H$ of weight $k$ , $c$ assigns positive weight only to maximum independent sets of $H$ , which are of size $|V(G)|$ .

These statements also hold, mutatis mutandis for $\chi _c^\bullet$ and correspondence-covers.

Proof. The first statement follows from the second; the existence of a fractional colouring supported only on maximum independent sets implies that every vertex is contained in a maximum independent set.

The second statement is a simple consequence of the bound $\chi _f(H) \ge N/\alpha$ that holds for any $N$ -vertex graph $H$ with independence number $\alpha$ . Every $k$ -fold list-cover $H$ of $G$ has $|V(H)|=k|V(G)|$ and $\alpha (H)\le |V(G)|$ , with equality when $k\ge \chi _\ell (G)$ . So if $\chi _f(H) = k = |V(H)|/\alpha (H)$ , we have equality. Now, if $c$ is a fractional colouring of $H$ of weight $k$ , which we interpret as a probability distribution on independent sets $I$ of $H$ such that $\mathop{\mathbb{P}}\nolimits _c(x\in I)\ge 1/k$ for each $x\in V(H)$ , we have

\begin{equation*} |V(G)| = \alpha (H) \ge \mathop {\mathbb {E}}\nolimits _c|I| = \sum _{v\in V(H)}\mathop {\mathbb {P}}\nolimits _c(v\in I) \ge |V(H)|/k = |V(G)|, \end{equation*}

and hence every $I$ with positive probability has size $|V(G)|$ .

The same proofs work in exactly the same way for correspondence packing.

By the previous, it is not hard to see that the following is an alternative, equivalent definition for the fractional list packing number.

Definition. Given a $k$ -list-assignment $L$ of $G$ , a fractional $L$ -packing of $G$ is (for some $m \in \mathbb{Z}^+$ ) a collection of $mk$ (not necessarily distinct) proper $L$ -colourings $c_1,\dots,c_{mk}$ of $G$ , such that for every $v \in V$ and $c \in L(v)$ there are $m$ values $i \in [mk]$ for which $c_i(v)=c.$ The smallest value of $k$ for which a fractional $L$ -packing of $G$ exists for every $k$ -list-assignment $L$ of $G$ , is the fractional list packing number $\chi ^\bullet _\ell (G).$

When working with explicit covers, we will often consider permutations of sets such as $\{1,2,3,4\}$ and $\{1_x,2_x,3_x\}$ endowed with a natural order that we assume is clear. It can be convenient to omit the subscripts, and usually we write a permutation of the set as an ordered sequence of comma-separated values, such as $f=(2,1,3)$ for the permutation $f$ with $f(1)=2$ , $f(2)=1$ , $f(3)=3$ . We do use standard cycle notation for transpositions, e.g. $(1\, 2)$ is a permutation of any ground set containing $\{1,2\}$ that swaps $1$ and $2$ . The ground set will be clear from context.

We will use the following formulation of Hall’s marriage theorem [16].

Hall’s marriage theorem ([16]). Given a family $\mathcal{F}$ of finite subsets of some ground set $X$ , where the subsets are counted with multiplicity, suppose $\mathcal{F}$ satisfies the marriage condition, that is that for each subfamily $\mathcal{F}^{\prime} \subseteq \mathcal{F}$

\begin{align*} |\mathcal{F}^{\prime}| \le{\left |\bigcup _{A\in{\mathcal{F}}^{\prime}} A\right |}. \end{align*}

Then there is an injective function $f\,:\, \mathcal{F}\to X$ such that $f(A)$ is an element of the set $A$ for every $A\in \mathcal{F}$ , that is, the image $f(\mathcal{F})$ is a system of distinct representatives of $\mathcal{F}$ .

This can also be stated in the terminology of matchings in bipartite graphs.

Theorem 12 (Hall’s marriage theorem, graph theoretic formulation). If $G=(A \cup B,E)$ is a bipartite graph for which $\lvert N(A_1) \rvert \ge \lvert A_1 \rvert$ for every $A_1 \subseteq A$ , then $G$ has a (maximum) matching of size $\lvert A \rvert$ .

1.2 Outline of the paper

The proofs for the upper bounds of the packing numbers of maximum degree $2,3$ , and $4$ are given in the corresponding Sections 2, 3, and 4. In Section 5, we give some results on fractional packing numbers. Finally, in Section 6, we conclude with observations on list packing of edge-colourings, possible variants of Brooks’ theorem, and comments on algorithmic aspects.

2. Paths and cycles

In this section, we determine the list and correspondence packing numbers for graphs with maximum degree $2$ , the connected examples of which are paths and cycles. The main work is for cycles. For the list packing number, we prove that for a particular edge $uv$ , a partial list-packing of $C_n \setminus uv$ can be extended simultaneously to both $u$ and $v$ . For the correspondence packing number, we prove that it is strictly larger than $3$ by giving a construction.

Theorem 13. For $n\ge 2$ , the list packing number of the $n$ -vertex path $P_n$ is $2$ . For $n\ge 3$ , the list packing number of the cycle $C_n$ is $3$ .

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.

Theorem 14. For $n\ge 2$ , the correspondence packing number of the $n$ -vertex path $P_n$ is $2$ . For $n\ge 3$ , the correspondence packing number of the cycle $C_n$ is $4$ .

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.

Figure 1. Correspondence-covers of cycles used in the proof of Theorem 14. For clarity, we omit the cliques on the sets $L(v)$ .

Proposition 2 on the packing numbers of cycles is a direct consequence of Theorems 13 and 14. Using this we can also characterise the graphs with packing numbers $2$ .

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$ .

We note in passing that Proposition 1 and Proposition 2 imply that no graph $G$ exists for which $\chi _c^\star (G)=3.$ In [7], it is proved that $3$ is the only positive integer that cannot be attained by the correspondence packing number.

3. Subcubic graphs

In this section, we prove that both the list and correspondence packing numbers of subcubic graphs are at most $4$ . Here, it is sufficient to consider cubic graphs because a connected subcubic graph which is not 3-regular has degeneracy at most $2$ , in which case the result follows from Theorem 5. The idea of extending an $L$ -packing of $G \setminus \{u,v\}$ , as done in Section 2, does not always work in 3-regular graphs. As such, we need to do substantially more work. First, we verify the case $K_4$ separately, by a computer search over all $4$ -fold correspondence-covers of $K_4$ . In a 3-regular graph that is not $K_4$ , we can take an edge $uv$ which does not belong to any triangle, and then consider partial packings of an even smaller subgraph than $G \setminus \{u,v\}$ , as we must also take some care when packing certain neighbours of $u$ and $v$ . Finishing the proof requires an argument similar to the proof of Theorem 13, where we show that there must be a valid extension to both $u$ and $v$ that is also valid for the edge $uv$ , but there are so many cases to check that it is convenient to verify them with computer assistance.

Theorem 15. For every graph $G$ with maximum degree $\Delta (G)\le 3$ , we have $\chi _{\ell }^\star (G) \le \chi _{c}^\star (G) \le 4$ .

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 [5, 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,1 and Yuster did in [27, 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.

Claim 16. Every connected cubic graph $G$ which is not equal to $K_4$ , has an edge $uv$ which is not part of a triangle.

Proof. Assume not. Let $a\in G$ be a vertex with $3$ neighbours $b$ , $c$ and $d$ . The edges $ab, ac$ and $ad$ all belong to a triangle. This implies that there are at least $2$ triangles containing $a$ and there cannot be $3$ triangles containing $a$ as otherwise $G[\{a,b,c,d\}]$ would be isomorphic to $K_4$ . Without loss of generality, assume that $abc$ and $acd$ are triangles, and the edge $bd$ is the only edge missing. Let $e$ be the third neighbour of $d$ . Since $a$ and $c$ already have degree $3$ , they are not neighbours of $e$ . As such, $d$ and $e$ have no common neighbours, implying that $de$ is an edge not belonging to 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 program2 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 [1]”. 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 [4]” in the code. Going through the $112$ bad triples at “In [3]”, 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 [2]”). 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 [5]”). For the latter, we verify at “In [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$ .

4. Larger maximum degree

In this section, we improve the upper bound $\chi _c^\star (G)\le 2\Delta (G)$ (which follows from Theorem 5) whenever $\Delta (G) \ge 4$ . The method is a more careful analysis of Hall’s marriage theorem, the main technique for proving Theorem 5. For $\Delta (G)=4$ , this results in a sharp upper bound for the correspondence packing number.

We start by stating some specific corollaries of Hall’s marriage theorem. The first version is just for completeness, but also indicates the nice structure of the counterexamples in the case when the conditions in Hall’s marriage theorem are almost met.

Lemma 17. Let $G=(A \cup B,E)$ be a bipartite graph with $\lvert A \rvert = \lvert B \rvert = 2m+1$ and minimum degree $m\ge 1$ . Then for every $A_1 \subseteq A$ , we have that $\lvert N(A_1) \rvert \ge \lvert A_1 \rvert$ except possibly if $G$ has two disjoint induced subgraphs $K_{m,m+1}$ as subgraphs in the following way. There are sets $A_1,A_2,B_1, B_2$ such that $A=A_1 \cup A_2, B=B_1 \cup B_2$ and $\lvert A_1 \rvert = \lvert B_2 \rvert = m+1$ and $\lvert A_2 \rvert = \lvert B_1 \rvert = m$ such that $G[A_1,B_1]$ and $G[A_2,B_2]$ are both isomorphic to $K_{m,m+1}$ and $G[A_1,B_2]$ is an empty graph.

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.

Figure 3. A bipartite graph $G \subset K_{5,5}$ with minimum degree two and without a perfect matching.

Next, we consider the case where the minimum degree is $m-1$ and the partition classes have size $2m$ .

Lemma 18. Let $G=(A \cup B,E)$ be a bipartite graph with $\lvert A \rvert = \lvert B \rvert = 2m$ and minimum degree $m-1$ for some $m \ge 2$ . Then for every $A_1 \subseteq A$ , we have that $\lvert N(A_1) \rvert \ge \lvert A_1 \rvert$ except possibly for

1. 1. $\lvert A_1 \rvert =m$ and $\lvert N(A_1) \rvert =m-1$

2. 2. $\lvert A_1 \rvert =m+1$ and $\lvert N(A_1) \rvert =m-1$

3. 3. $\lvert A_1 \rvert =m+1$ and $\lvert N(A_1) \rvert =m$

Let $A_2=A \setminus A_1$ , $B_1=N(A_1)$ , and $B_2=B\setminus B_1$ . Then we have that $G[A_1,B_2]$ is the empty graph, and respectively the following hold:

1. 1. $G[A_1,B_1]\cong K_{m,m-1}$ ,

2. 2. $G[A_1,B_1]\cong K_{m+1,m-1}$ and $G[A_2,B_2]\cong K_{m-1,m+1}$ ,

3. 3. $G[A_2,B_2]\cong K_{m-1,m}$

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.

Figure 4. Examples of bipartite graphs $G \subset K_{6,6}$ with $\delta (G)=2=m-1$ and without a perfect matching. Red edges present some potential missing edges in a $K_{m,m+1}$ . Blue edges present potential edges that can be added.

We are now ready to prove Theorem 6, which we recall states that for $\Delta \ge 4$ , if $G$ is a graph of maximum degree $\Delta$ then $\chi ^\star _c(G) \leq 2\Delta (G)-2$ .

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 [5, 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.

Claim 19. Let $G=(A \cup B,E)$ be a bipartite graph with $\lvert A \rvert = \lvert B \rvert = 2m$ and minimum degree $m$ for some $m \ge 3$ . Let $A=A_1 \cup A_2$ and $B=B_1 \cup B_2$ be partitions such that $\lvert A_1\rvert =m, \lvert B_1\rvert =m-1$ , $G[A_1,B_1]\cong K_{m,m-1}$ , and $G[A_1,B_2]\cong mK_2+K_1$ . Then for a matching $M$ that contains at most $m-2$ edges of $G([A_1,B_2])$ , $G \setminus M$ satisfies the conditions of Theorem  12 .

Proof. In this proof, every neighbourhood will be a neighbourhood in the graph $G \setminus M$ , i.e., with $N$ we refer here to $N_{G \setminus M}$ . Let $b$ be the only vertex in $B$ which has no neighbour in $G$ belonging to $A_1$ .

Take $B^{\prime} \subseteq B$ . Since $G \setminus M$ has minimum degree $\geq m-1$ , we have $\lvert B^{\prime} \rvert \le \lvert N(B^{\prime}) \rvert$ if $\lvert B^{\prime} \rvert \not \in \{m,m+1\}$ , as explained before in the proof of Lemma 18. So now assume that $\lvert B^{\prime} \rvert \in \{m,m+1\}$ . We consider three cases.

If $\lvert B^{\prime} \cap B_1 \rvert \ge 2$ , then $A_1 \subseteq N(B^{\prime})$ and every vertex in $B^{\prime} \cap B_2$ has at least $m-2\ge 1$ neighbours in $A_2$ . Thus $\left |N(B^{\prime})\right | \ge \left |A_1\right |+1= m+1 \ge \left |B^{\prime}\right |$ .

If $b \in B^{\prime} \subseteq B_2$ , then $\left |N(b) \cap A_2\right | \ge m-1$ and $\left | N(B^{\prime})\cap A_1 \right | \ge \left |B^{\prime}\right | -1-(m-2)$ (by choice of $M$ ). So we conclude that $\left |N(B^{\prime})\right | \ge \left |N(b) \cap A_2\right | + \left | N(B^{\prime}) \cap A_1\right | \ge \left |B^{\prime}\right |$ .

If $b \not \in B^{\prime} \subseteq B_2$ (so $B^{\prime}=B_2 \setminus b$ ), then $\left |N(B^{\prime}) \cap A_2\right | \ge m-2$ and $\left | N(B^{\prime}) \cap A_1\right | \ge m -(m-2)=2$ (at most $m-2$ edges of the matching between $A_1$ and $B^{\prime}$ are removed) and the conclusion follows again.

In the remaining case, $\lvert B^{\prime} \cap B_1 \rvert =1$ . The vertex $B^{\prime} \cap B_1$ has at least $m-1$ neighbours in $A_1$ . The vertices in $B^{\prime} \cap B_2$ have at least $m-2$ neighbours in $A_2$ . If $\left |B^{\prime}\right |=m$ , we conclude since $\left |N(B^{\prime})\right | \ge (m-1)+(m-2) \ge \left |B^{\prime}\right |$ . So we are left with $\left |B^{\prime}\right |=m+1$ and thus either $B^{\prime}\cap B_2 = B_2 \setminus b$ which implies that $A_1 \subseteq N(B^{\prime})$ , or $b \in B^{\prime}$ and $\left |N(b) \cap A_2\right | \ge m-1$ . In either case, we have $\left |N(B^{\prime})\right | \ge 2m-2 \ge m+1=\left |B^{\prime}\right |$ .

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$ .

Yuster [27] investigated factors of independent transversals in graphs, and stated a conjecture [27, Conj. 1.1] equivalent to the case of complete graphs in our Conjecture 3 (ii). Yuster proved that $\chi _c^\star (K_4)=4$ by computer verification, and stated that the general case of establishing tight upper bounds on $\chi _c^\star (K_n)$ is wide open. Theorem 6 immediately gives a tight upper bound for $n=5$ . That is, we now know that $\chi _c^\star (K_5)=6$ by a proof that does not involve computer verification.

At this point, we have completed the proofs of all the parts of Theorem 4. Combined with our previous results we can verify Conjectures 3 for small maximum degree.

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}$ .

5. Fractional results

We now prove Theorem 7, establishing fractional versions of Conjecture 3, where we find in part (ii) the rounding unnecessary. Theorem 7 is an immediate corollary of the following generalisation in terms of fractional colouring with local demands, a concept introduced in [18]. We do not require a careful discussion of fractional colouring with local demands here, but we point out that a fractional colouring of weight $k$ is equivalent to a probability distribution on independent sets of a graph such that for every vertex, the marginal probability of inclusion in the independent set is at least $1/k$ . Imposing local demands is a generalisation of this concept equivalent to allowing the required lower bound on the marginal probability to vary according to the vertex, as in the statement below. We remark that the inductive proof really requires this stronger hypothesis, and note that the argument will not work with degeneracy instead of maximum degree. Indeed we observe in Proposition 21 that the statement with maximum degree replaced by degeneracy is false.

Lemma 20. Let $G$ be a graph. Consider a correspondence-cover $(L,H)$ of $G$ , such that $|L(v)|\ge \deg (v)+1$ for each vertex $v$ of $G$ . Then there exists a probability distribution on independent sets $I$ of $H$ such that for every vertex $v$ of $G$ and every vertex $x\in L(v)$ of $H$ , we have $\mathop{\mathbb{P}}\nolimits (x \in I) \geq 1/ |L(v)|$ .

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 [6, Lemma 7.3] and its applications.

In [5, Prop. 24], we gave a construction of a (complete) bipartite graph $G$ with degeneracy $d$ but with $\chi _c^\star (G)=2d$ . Proposition 22 shows that for this same graph $G$ , $\chi _c^\bullet (G) \le d+1$ , implying Theorem 9(ii). The latter result raises the question of whether the fractional correspondence packing number can exceed $d+1$ in $d$ -degenerate graphs. We give an example showing even the fractional list packing number can. The construction is the one we gave in [5, Thm. 25], but we strengthen the analysis to show that in fact for the same graph $\chi _\ell ^\bullet (G)\ge d+2$ and thus Theorem 9(i) holds. For convenience, we repeat the construction here.

Proposition 21. For every $d \ge 2$ , there exists a graph $G$ with degeneracy $d$ for which $\chi _\ell ^\bullet (G)\ge d+2$ .

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$ .

Our next positive result is a version of the greedy bound for bipartite graphs where one is permitted to take the smaller of the maximum degrees over vertices in each part of a bipartition. In [5, Lem. 33], we showed the analogous upper bound for $\chi _\ell ^\star$ . Here, our bound applies to the fractional variant of correspondence packing as well, though the analogue for correspondence packing is false. In [5, Cor. 34], we showed that for every complete bipartite graph $K_{a,b}$ with $a\gt b^b$ , we have $\chi _{\ell }^{\star }(K_{a,b})=b+1$ while $\chi _c^{\star }(K_{a,b})=2b$ . This demonstrates a constant factor gap between list and correspondence packing numbers. The proposition below implies that $\chi _{\ell }^\bullet (K_{a,b})=\chi _c^\bullet (K_{a,b})=b+1$ for such $a$ and $b$ , demonstrating that the striking factor $2$ difference between list packing and correspondence packing in that construction disappears in the fractional relaxation.

Proposition 22. Let $G=(A \cup B, E)$ be a bipartite graph with parts $A$ and $B$ having maximum degrees $\Delta _A$ and $\Delta _B$ , respectively, where $\Delta _A \le \Delta _B$ . Then $\chi _\ell ^\bullet (G) \le \chi _c^\bullet (G) \le \Delta _A+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$ .

We conclude this section by noting that the two fractional packing numbers can be different from both the chromatic and integral packing numbers.

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 [10]. 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 verification3 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 [4, 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 verification4 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 [9]. The equality $\chi _c^\bullet (C_n)=3$ follows from Theorem 7. The equality $\chi _c^\star (C_n)=4$ is from Theorem 14.

6. Concluding remarks

A main objective in this paper was to more closely analyse the list packing number in fundamental settings, as a way to gain more intuition into the List Packing Conjecture; this led us naturally to the proposal of Conjecture 3. We put some evidence towards Conjecture 3 first by confirming it for graphs with small maximum degree. Restricted to complete graphs, Conjecture 3 (ii) coincides with Conjecture 1.1 in [27], which remains generally open but was previously verified for up to $4$ vertices. Here we confirmed it for the complete graph on $5$ vertices via the more general result that $\chi _c^{\star }(G) \leq 2\Delta -2$ for any graph $G$ with maximum degree $\Delta \geq 4$ .

We also proved an approximate version of Conjecture 3 via Theorem 7 and the introduction of fractional versions of the list and correspondence packing numbers. More generally in combinatorics, fractional packing often serves as a critical component in proving an asymptotically matching bound for the respective integral packing problem. Here though, in the context of correspondence packing, we noticed (see the remarks above and below Proposition 22) that the fractional and integral value actually can differ by a factor $2$ , an intriguing barrier to this approach.

We contend that the determination of $\chi _c^\bullet (G)$ may be an interesting problem in its own right. Just as for the original, integral form of list packing, several problems come to mind, especially the fractional versions of our main conjectures from [5], which we made explicit above in Conjecture 8. A resolution to such fractional questions could yield interesting insights into the List Packing Conjecture. An especially appealing problem is to determine an optimal upper bound on the fractional list packing number for planar graphs.

Conjecture 23. $\chi _\ell ^\bullet (G)\le 5$ for any planar graph $G$ .

While we have shown examples of graphs $G$ for which $\chi _c^\star (G)\sim 2\chi _c(G)$ [5, Prop. 24], we actually do not know any graph for which the list packing number is two larger than the list chromatic number. As such, the following is a natural challenge.

Problem 24. Find examples of graphs $G$ for which $\chi _{\ell }^\star (G)\gt \chi _{\ell }(G)+1$ .

In the following three subsections, we give some remarks related to some interesting further directions one could take to understand the list packing number better.

6.1 Many list-colourings but no list-packing, even for line graphs

By a theorem of Hall [15], for a $k$ -list-assignment $L$ of $K_k$ , there are at least $k!$ proper $L$ -colourings of $K_k$ . Because there are so many $L$ -colourings of $K_k$ , the fact that there exists a packing of $k$ disjoint $L$ -colourings might not seem especially surprising. Nevertheless, a packing of colourings does not necessarily follow from a large number of colourings.

Consider the Latin square $K_n \mathbin \square K_n$ as the graph with the cells of a $n \times n$ grid as its vertices, where two vertices are adjacent if they are in the same row or column. Denote the $n^2$ vertices of $K_n \mathbin \square K_n$ by pairs in $[n]^2$ , where $[n]=\{1,2,\ldots, n\}$ . Let the list-assignment $L$ of $K_n \mathbin \square K_n$ be given by $L((1,i))=[n+1]\setminus \{1\}$ for every $i \in [n]$ , $L((j,1))=[n+1]\setminus \{2\}$ for every $2 \le j \le n$ and $L((j,i))=[n]$ for every $2 \le i,j \le n$ . This assignment for $K_4 \mathbin \square K_4$ is presented in Table 1, while an example for $n=3$ and the general case is also presented in [20, Fig. 4.9, Fig 5.1].

Table 1 Lists on $K_4 \mathbin \square K_4$ without a packing of colourings

Extending an observation by Levit [20, Lem. 42], we prove the following.

Proposition 25. There are $n^{n^2(1-o(1))}$ $L$ -colourings of $K_n \mathbin \square K_n$ for the $n$ -list-assignment $L$ from above. Nevertheless, for every $n\ge 2$ , $K_n \mathbin \square K_n$ is not fractionally $L$ -packable and thus $\chi _\ell ^\star (K_n \mathbin \square K_n) \ge \chi _\ell ^\bullet (K_n \mathbin \square K_n)\gt n$ .

Proof. We first prove that there are at least $\frac{n-1}{n} N(n)$ many proper $L$ -colourings of $K_n \mathbin \square K_n$ , where $N(n)=n^{n^2(1-o(1))}$ denotes the number of Latin squares of order $n$ (see [26, Thm. 17.2]). A Latin square corresponds to a proper $n$ -colouring of $K_n \mathbin \square K_n$ . Take any such proper $n$ -colouring for which $(1,1)$ has not been coloured with $1$ . The vertex coloured by $1$ in the first column and the vertex coloured by $2$ in the first row (if it is not equal to $(1,1)$ ) are recoloured with $n+1$ . Then by definition, we have a proper $L$ -colouring of $K_n \mathbin \square K_n$ and the lower bound follows because this recolouring gives an injection from the set of Latin squares which do not have a $1$ in the top-left cell to the collection of proper $L$ -colourings of $K_n \mathbin \square K_n$ .

Next, we prove that $K_n \mathbin \square K_n$ is not fractionally $L$ -packable (i.e. the associated cover has fractional chromatic number strictly larger than $n$ ). It is enough (by Proposition 11) to show that there does not exist a proper $L$ -colouring that colours $(1,1)$ with $n+1$ . Note that if such a colouring were to exist, the other vertices of the first column would use every colour in $[n]\setminus \{1\}$ , and the other vertices of the first row would use every colour in $[n]\setminus \{2\}$ . As such, every colour in $[n]$ can be used at most $n-2$ times on the vertex subset $([n]\setminus 1)\times ([n]\setminus 1)$ . Since $(n-1)^2\gt n(n-2)$ , this implies that the colouring cannot be extended.

So even while there are about as many proper $L$ -colourings of the graph as one can hope for, the graph is not fractionally $L$ -packable.

Note that $K_n \mathbin \square K_n$ is the line graph of the complete bipartite graph $K_{n,n}$ . It is immediate that $K_n \mathbin \square K_n$ has chromatic number $n$ . As proposed by Dinitz and proved by Galvin (see [11]), the list chromatic number of this graph equals $n$ as well. However, Proposition 25 indicates that the packing version of Dinitz’ problem behaves differently from the colouring version, as the list packing number of $K_n \mathbin \square K_n$ exceeds $n$ . We ask a question that arises from this observation.

Conjecture 26 (Packing version of Dinitz’s problem). For $n \ge 3$ , $\chi _\ell ^\star (K_n \mathbin \square K_n)=n+1$ .

A possible approach, which is similar to that used in [24], is to prove that

\begin{equation*} \chi _\ell (K_n \mathbin \square K_n \mathbin \square K_{n+1})=n+1.\end{equation*}

This would imply the result due to the observation that $\chi _\ell (G \mathbin \square K_m)=m$ implies that $\chi _\ell ^\star (G) \le m.$ The latter implication is immediate by choosing the same list for the $m$ copies of a particular vertex.

6.2 Variants of brooks’ theorem

A natural Brooks’-type theorem for list packing is false. The diamond $K_4^-$ is formed by removing an edge from the complete graph $K_4$ . The $K_4^-$ -necklace $G$ , consisting of two $K_4^-$ s whose degree $2$ vertices are pairwise connected, is a $3$ -regular graph (that is not $K_4$ ) for which $\chi _{\ell }^\bullet (G)=\chi _\ell ^\star (G)=4$ . See Fig. 7 for a $3$ -list-assignment $L$ that does not admit a fractional $L$ -packing. This can easily be verified by a computer,5 though manual verification is feasible. The example proves Theorem 9(iii). An interesting feature of this example is that an $L$ -colouring extending any single mapping $c(v) = x$ for $x\in L(v)$ exists.

Figure 7. The $K_4^-$ -necklace and a list-assignment for which no (fractional) list-packing is possible.

While we rule out the statement $\chi _\ell ^\bullet (G)\le \max \{3,\omega (G),\Delta (G)\}$ , which seems an appealing formulation because cycles have list packing number $3$ , it is plausible that a Brooks’-type theorem holds with a more esoteric set of exceptional cases. For example, we have not ruled out a bound of the form $\chi _\ell ^\bullet (G)\le \max \{4,\omega (G),\Delta (G)\}$ , or that there exists an easily-describable set of graphs $\mathcal G$ (including cycles and the $K_4^-$ -necklace) such that for connected $G\notin \mathcal G$ we have $\chi _\ell ^\star (G)\le \max \{\omega (G),\Delta (G)\}$ . We suggest the following question.

Problem 27. Characterise the graphs of maximum degree $3$ with list packing number $4$ .

For correspondence packing, analogues of Brooks’ theorem and Reed’s conjecture need to be modified markedly. We remark6 that the Petersen graph $P_{5,2}$ satisfies $\chi _c^\star (P_{5,2})\ge 4$ , while it is triangle-free and has maximum degree $3$ . The even degree case of Conjecture 3 is the upper bound $\chi _c^\star (G)\le \Delta +2$ , and we ask whether $K_5$ the only tight example for $\Delta (G)=4$ .

Problem 28. Characterise the graphs of maximum degree $4$ with correspondence packing number $6$ .

Seeking a packing of list-colourings requires a list-assignment with uniform list sizes, but the fractional variant of list packing naturally generalises to list-assignments with arbitrary list sizes. For a list-assignment $L$ of $G$ , we can ask for a probability distribution on independent sets $I$ of the associated list-cover $(\tilde L,H)$ , where $\tilde L(v) = \{i_v : i\in L(v)\}$ , such that for each $v\in V(G)$ and $i\in L(v)$ , $\mathop{\mathbb{P}}(i_v\in I) \ge 1/|L(v)|$ (see [18] for the general theory of fractional colouring with local demands). With this, it makes sense to study fractional degree-list-packability as a more structured version of degree-choosability. A graph $G$ is degree-choosable if, for any list-assignment $L$ such that $|L(v)|=\deg (v)$ , $G$ admits an $L$ -colouring. Erdős, Rubin and Taylor [10], and independently Borodin [3] classified the degree-choosable graphs as those which are not Gallai trees. Here, we note that fractional degree-list-packability can be defined as above for list-assignments with $|L(v)|=\deg (v)$ , but point out that the proof for degree-choosability does not extend to this notion because of the $K_4^-$ -necklace. It is not too hard to come up with irregular examples too, such as the graph $K_4^-$ itself with lists $\{1,2\}$ , $\{1,3\}$ , $\{1,2,3\}$ , $\{1,2,3\}$ , and $K_5^-$ with lists $\{1,2,3\}$ , $\{1,2,4\}$ , and three copies of $\{1,2,3,4\}$ . We give a computer verification of the former7 that is easily adapted to give the latter.

Problem 29. Characterise the graphs that are fractionally degree-list-packable.

6.3 Algorithms and complexity

At the heart of many combinatorial problems sits some inherently difficult algorithmic tasks (and vice versa). The list packing problem is no exception. Furthermore, many intuitively algorithmic tactics we could successfully employ for the corresponding graph colouring problems become blunted in the hunt for list-packings. Most especially, local modifications of the choice applied at one particular vertex or in its neighbourhood become harder to reason about. We therefore believe that the algorithmic aspects of list packing are a promising research line, and here we make some basic comments based on our results. Further study would be interesting; in particular, the nature of the list packing number makes it natural to explore various classes of graphs, as is common in algorithmic graph theory.

The decision problem associated to list colouring is ‘graph $k$ -list colouring’, where an instance is a graph $G$ and we must decide whether $\chi _\ell (G)\le k$ . We can define an analogous problem ‘graph $k$ -list packing’, and relate its complexity to the list colouring problem. It is well-known that for $k\ge 3$ , ‘graph $k$ -list colouring’ is complete for the complexity class $\Pi _2^{\mathsf{p}}=\mathsf{coNP}^{\mathsf{NP}}$ (in the second level of the polynomial hierarchy) of problems for which a Turing machine with access to an oracle for $\mathsf{NP}$ can verify certificates for ‘no’ instances in polynomial time [10,14]. By the classification of languages in $\Pi _2^{\mathsf{p}}$ according to a description in terms of quantified Boolean formulae, i.e. $L\in \Pi _2^{\mathsf{p}}$ if and only if there is a constant $c$ and language $R\in \mathsf{P}$ such that

\begin{equation*} L = \{x \,:\, \forall y \exists z \,:\, |y|,|z| \le |x|^c,\text { and }(x,y,z) \in R\}, \end{equation*}

it is easy to see that graph $k$ -list packing lies in the same complexity class $\Pi _2^{\mathsf{p}}$ . That is, although combinatorially it seems harder to find a packing than a single list-colouring, there is no difference in computational complexity (at this resolution). We raise the question of completeness, and the fact that $\Pi _2^{\mathsf{p}}$ -completeness for the closely related ‘strong $k$ -colouring’ decision problem is open [25].

Question 30. Is there some $k_0$ such that for all $k\ge k_0$ , graph $k$ -list packing is complete for the complexity class $\Pi _2^{\mathsf{p}}$ ? Is $k_0=3$ ?

The classification of graphs of list chromatic number $2$ in [10] shows that graph $2$ -list colouring is in $\mathsf{P}$ . Similarly, Proposition 1 shows that graph $2$ -list packing is in $\mathsf{P}$ . In much the same way, the fact that for all $k$ , graph $k$ -list packing restricted to instances of maximum degree $2$ is in $\mathsf{P}$ follows from Proposition 1 and Proposition 2. The correspondence version of the above question is also natural.

Algorithms that construct in polynomial time list-colourings, list-packings, and more general objects such as independent transversals and strong colourings, have been studied for some time (e.g. [12,13,17]). We first observe that many of our results give linear-time constructions.

Remark 31. The proofs in Sections  2 , 3 and 4 give rise to constructions of the desired packings with algorithms that run in linear time (as a function of the order $n$ of $G$ and supposing that the maximum degree is fixed). Note that Claim  16 actually implies that there is an edge not belonging to a triangle near every vertex of a $3$ -regular graph that is not $K_4$ . Knowing that there do exist linear time algorithms [22] (again, assuming that the maximum degree is fixed) to derive the degeneracy ordering of $G \setminus v$ and also finding the greedy packing happens in linear time, we conclude easily. Completing the packing is something that happens locally.

One of the most general algorithmic results, due to Graf and Haxell [13, Cor. 26], can be used to construct list- and correspondence-packings of graphs of maximum degree $\Delta$ and when lists are of size at least $3\Delta +1$ (see [1] for the key method that gives a non-constructive version of this result). Their result actually applies to strong colouring, which is considerably more general than correspondence packing, see e.g. [5]. Here, it suffices to note that finding a $k$ -colouring of a $k$ -fold correspondence-cover $(L,H)$ of a graph $G$ of maximum degree $\Delta$ is a special case of finding a strong $k$ -colouring of a graph $H^\star$ of maximum degree $\Delta$ . This is by removing the cliques on the lists in $H$ and finding a strong colouring with respect to the partition induced by $L$ . We showed before [5, Thms. 3 and 10] that the method of [1] applied in the context of list and correspondence packing gives the bounds

\begin{align*} \chi _\ell ^\star (G) &\le 1+\Delta (G)+\chi _\ell (G),& \chi _c^\star (G) &\le 1+\Delta (G)+\chi _c(G),& \end{align*}

though we did not give constructive proofs of these bounds. Somewhat interestingly, we note that Theorem 5 gives a polynomial-time construction for list- and correspondence-packings with lists of size $2\Delta$ . That is, we significantly reduce the required lower bound on the size of the partition classes (equivalent to list size) in one of the results of [13], at the considerable cost of requiring that the graph we colour is a cover of some bounded-degree graph.