List packing number of bounded degree graphs

Journal article (2024)

Authors

Stijn Cambie Institute for Basic Science (IBS), Katholieke Universiteit Leuven
W.P.S. Cames van Batenburg Discrete Mathematics and Optimization - EEMCS
Ewan Davies Colorado State University
Ross J. Kang Universiteit van Amsterdam
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
More Info
expand_more

Published Date

2024

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.