List packing number of bounded degree graphs

被引：1

作者：

Cambie, Stijn ^{[1
,2
]}

van Batenburg, Wouter Cames ^{[3
]}

Davies, Ewan ^{[4
]}

Kang, Ross J. ^{[5
]}

机构：

[1] Inst Basic Sci IBS, Extremal Combinator & Probabil Grp ECOPRO, Daejeon, South Korea

[2] Katholieke Univ Leuven, Dept Comp Sci, Campus Kulak Kortrijk, B-8500 Kortrijk, Belgium

[3] Delft Univ Technol, Delft Inst Appl Math, Delft, Netherlands

[4] Colorado State Univ, Dept Comp Sci, Ft Collins, CO USA

[5] Univ Amsterdam, Korteweg de Vries Inst Math, Amsterdam, Netherlands

来源：

COMBINATORICS PROBABILITY AND COMPUTING | 2024年 / 33卷 / 06期

关键词：

Packing of list colourings; list packing number; list colouring; correspondence colouring; maximum degree; transversals;

D O I：

10.1017/S0963548324000191

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：807 / 828

页数：22

共 50 条

[21] Bounds on the Generalised Acyclic Chromatic Numbers of Bounded Degree Graphs
Catherine Greenhill
Oleg Pikhurko
Graphs and Combinatorics, 2005, 21 : 407 - 419
[22] The energy of C4-free graphs of bounded degree
Nikiforov, V.
LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (11-12) : 2569 - 2573
[23] Maximizing the number of independent subsets over trees with bounded degree
Heuberger, Clemens
Wagner, Stephan G.
JOURNAL OF GRAPH THEORY, 2008, 58 (01) : 49 - 68
[24] A smaller upper bound for the list injective chromatic number of planar graphs
Chen, Hongyu
Zhang, Li
AIMS MATHEMATICS, 2025, 10 (01): : 289 - 310
[25] Improved lower bound for the list chromatic number of graphs with no Kt minor
Steiner, Raphael
COMBINATORICS PROBABILITY & COMPUTING, 2022, 31 (06) : 1070 - 1075
[26] Total chromatic number of planar graphs with maximum degree ten
Wang, Weifan
JOURNAL OF GRAPH THEORY, 2007, 54 (02) : 91 - 102
[27] Packing Colourings in Complete Bipartite Graphs and the Inverse Problem for Correspondence Packing
Cambie, Stijn
Haemaelaeinen, Rimma
JOURNAL OF GRAPH THEORY, 2025, 109 (01) : 52 - 61
[28] A list version of graph packing
Gyori, Ervin
Kostochka, Alexandr
McConvey, Andrew
Yager, Derrek
DISCRETE MATHEMATICS, 2016, 339 (08) : 2178 - 2185
[29] A characterization of graphs with given maximum degree and smallest possible matching number
Henning, Michael A.
Shozi, Zekhaya B.
DISCRETE MATHEMATICS, 2021, 344 (07)
[30] The entire chromatic number of graphs embedded on the torus with large maximum degree
Hu, Xiaoxue
Wang, Ping
Wang, Yiqiao
Wang, Weifan
THEORETICAL COMPUTER SCIENCE, 2017, 689 : 108 - 116

← 1 2 3 4 5 →