List packing number of bounded degree graphs

Open Access
Authors
Publication date 11-2024
Journal Combinatorics Probability and Computing
Volume | Issue number 33 | 6
Pages (from-to) 807-828
Organisations
  • Faculty of Science (FNWI) - Korteweg-de Vries Institute for Mathematics (KdVI)
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 δ has list packing number at most Δ+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.  
Document type Article
Language English
Published at https://doi.org/10.1017/S0963548324000191
Other links https://www.scopus.com/pages/publications/85205051174
Downloads
Permalink to this page
Back