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 条
  • [32] Number of vertices of degree three in spanning 3-trees in square graphs
    Aye, Win Min
    Tian, Tao
    Xiong, Liming
    APPLIED MATHEMATICS AND COMPUTATION, 2019, 357 : 258 - 262
  • [33] A characterization of graphs with given maximum degree and smallest possible matching number: II
    Henning, Michael A.
    Shozi, Zekhaya B.
    DISCRETE MATHEMATICS, 2022, 345 (03)
  • [34] On connected list colorings of graphs
    Vizing, VG
    DISCRETE APPLIED MATHEMATICS, 2001, 114 (1-3) : 295 - 300
  • [35] Bounded transversals in multipartite graphs
    Berke, Robert
    Haxell, Penny
    Szabo, Tibor
    JOURNAL OF GRAPH THEORY, 2012, 70 (03) : 318 - 331
  • [36] Packing d-degenerate graphs
    Bollobas, Bela
    Kostochka, Alexandr
    Nakprasit, Kittikorn
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (01) : 85 - 94
  • [37] 2-distance choice number of planar graphs with maximal degree no more than 4
    Zhou, Wenjuan
    Sun, Lei
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (05)
  • [38] Facial list colourings of plane graphs
    Fabrici, Igor
    Jendrol, Stanislav
    Voigt, Margit
    DISCRETE MATHEMATICS, 2016, 339 (11) : 2826 - 2831
  • [39] List injective coloring of planar graphs
    Cai, Jiansheng
    Li, Wenwen
    Cai, Wenjing
    Dehmer, Matthias
    APPLIED MATHEMATICS AND COMPUTATION, 2023, 439
  • [40] Average eccentricity, minimum degree and maximum degree in graphs
    Dankelmann, P.
    Osaye, F. J.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (03) : 697 - 712