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
关键词
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 条
  • [1] Equitable List Coloring of Graphs with Bounded Degree
    Kierstead, H. A.
    Kostochka, A. V.
    JOURNAL OF GRAPH THEORY, 2013, 74 (03) : 309 - 334
  • [2] Total interval number for graphs with bounded degree
    Kostochka, AV
    West, DB
    JOURNAL OF GRAPH THEORY, 1997, 25 (01) : 79 - 84
  • [3] ON PACKING TWO GRAPHS WITH BOUNDED SUM OF SIZES AND MAXIMUM DEGREE
    Zak, Andrzej
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2014, 28 (04) : 1686 - 1698
  • [4] Acyclic Choosability of Graphs with Bounded Degree
    Wang, Juan
    Miao, Lian Ying
    Li, Jin Bo
    Liu, Yun Long
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2022, 38 (03) : 560 - 570
  • [5] Acyclic Choosability of Graphs with Bounded Degree
    Juan Wang
    Lian Ying Miao
    Jin Bo Li
    Yun Long Liu
    Acta Mathematica Sinica, English Series, 2022, 38 : 560 - 570
  • [6] Maximizing the density of Kt's in graphs of bounded degree and clique number
    Kirsch, R.
    Radcliffe, A. J.
    DISCRETE MATHEMATICS, 2020, 343 (06)
  • [7] Cycle transversals in bounded degree graphs
    Groshaus, Marina
    Hell, Pavol
    Klein, Sulamita
    Nogueira, Loana Tito
    Protti, Fabio
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2011, 13 (01) : 45 - 66
  • [8] Decreasing the diameter of bounded degree graphs
    Alon, N
    Gyárfás, A
    Ruszinkó, M
    JOURNAL OF GRAPH THEORY, 2000, 35 (03) : 161 - 172
  • [9] The list chromatic number of graphs with small clique number
    Molloy, Michael
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 264 - 284
  • [10] Filling the complexity gaps for colouring planar and bounded degree graphs
    Dabrowski, Konrad K.
    Dross, Francois
    Johnson, Matthew
    Paulusma, Daniel
    JOURNAL OF GRAPH THEORY, 2019, 92 (04) : 377 - 393