2024/10/03 by Cambie, Stijn, van Batenburg, Wouter Cames · 1 citation
#05C15 #05C70 #05c85 #05d15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2410.02695
The fractional list packing number χℓ\bullet(G) of a graph G is a graph invariant that has recently arisen from the study of disjoint list-colourings. It measures how large the lists of a list-assignment L:V(G)→ 2ℕ need to be to ensure the existence of a `perfectly balanced' probability distribution on proper L-colourings, i.e., such that at every vertex v, every colour appears with equal probability 1/|L(v)|. In this work we give various bounds on χℓ\bullet(G), which admit strengthenings for correspondence and local-degree versions. As a corollary, we improve theorems on the related notion of flexible list colouring. In particular we study Cartesian products and d-degenerate graphs, and we prove that χℓ\bullet(G) is bounded from above by the pathwidth of G plus one. The correspondence analogue of the latter is false for treewidth instead of pathwidth.