List Packing and Correspondence Packing of Planar Graphs

Abstract

For a graph $G$ and a list assignment $L$ with $|L(v)|=k$ for all $v$, an $L$-packing consists of $L$-colorings ${\phi }_1,\cdots ,{\phi }_k$ such that ${\phi }_i(v)\ne {\phi }_j(v)$ for all $v$ and all distinct $i,j\in \{1,\dots ,k\}$. Let ${\chi }_{\ell }^{\star }(G)$ denote the smallest $k$ such that $G$ has an $L$-packing for every $L$ with $|L(v)|=k$ for all $v$. Let ${\mathcal{P}}_k$ denote the set of all planar graphs with girth at least $k$. We show that (i) ${\chi }_{\ell }^{\star }(G)\le 8$ for all $G\in {\mathcal{P}}_3$ and (ii) ${\chi }_{\ell }^{\star }(G)\le 5$ for all $G\in {\mathcal{P}}_4$ and (iii) ${\chi }_{\ell }^{\star }(G)\le 4$ for all $G\in {\mathcal{P}}_5$. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also construct outerplanar graphs $G$ such that ${\chi }_{\ell }^{\star }(G)=4$, which matches the known upper bound ${\chi }_{\ell }^{\star }(G)\le 4$ for all outerplanar graphs. Finally, we consider the analogue of ${\chi }_{\ell }^{\star }$ for correspondence coloring, ${\chi }_c^{\star }$. In fact, all bounds stated above for ${\chi }_{\ell }^{\star }$ also hold for ${\chi }_c^{\star }$.

20 pages, 15 figures, 2nd version incorporates reviewer feedback, to appear in J. of Graph Theory; 3rd version updates title to match the final journal version