List Packing and Correspondence Packing of Planar Graphs

ABSTRACT For a graphGand a list assignmentLwith∣ L ( v ) ∣ = kfor allv, anL‐packing consists ofL‐coloringsφ 1 , … , φ ksuch thatφ i ( v ) ≠ φ j ( v )for allvand all distincti , j ∈ { 1 , … , k }. Letχ ℓ ⋆ ( G )denote the smallestksuch thatGhas anL‐packing for everyLwith∣ L ( v ) ∣ = kfor allv. LetP kdenote the set of all planar graphs with girth at leastk. We show that (i)χ ℓ ⋆ ( G ) ⩽ 8for allG ∈ P 3and (ii)χ ℓ ⋆ ( G ) ⩽ 5for allG ∈ P 4and (iii)χ ℓ ⋆ ( G ) ⩽ 4for allG ∈ P 5. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also consider the analogue ofχ ℓ ⋆for correspondence coloring,χ c ⋆. In fact, all bounds stated above forχ ℓ ⋆also hold forχ c ⋆.