List packing number of bounded degree graphs

MaRDI QIDQ6428196zbMATH OpenFDO

Authors Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies, Ross J. Kang

Publication date 2 March 2023

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $Delta$ has list packing number at most $Delta+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.

This page was built for publication: List packing number of bounded degree graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428196)