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 条
  • [41] Edge-face chromatic number of 2-connected plane graphs with high maximum degree
    Zhang Zhongfu
    Wang Weifan
    Li Jingwen
    Yao Bing
    Bu Yuehua
    ACTA MATHEMATICA SCIENTIA, 2006, 26 (03) : 477 - 482
  • [42] DEGREE DISTANCE OF UNICYCLIC GRAPHS
    Du, Zhibin
    Zhou, Bo
    FILOMAT, 2010, 24 (04) : 95 - 120
  • [43] Average eccentricity, minimum degree and maximum degree in graphs
    P. Dankelmann
    F. J. Osaye
    Journal of Combinatorial Optimization, 2020, 40 : 697 - 712
  • [44] EDGE-FACE CHROMATIC NUMBER OF 2-CONNECTED PLANE GRAPHS WITH HIGH MAXIMUM DEGREE
    张忠辅
    王维凡
    李敬文
    姚兵
    卜月华
    Acta Mathematica Scientia, 2006, (03) : 477 - 482
  • [45] Acyclic list edge coloring of outerplanar graphs
    Shu, Qiaojun
    Wang, Yiqiao
    Wang, Weifan
    DISCRETE MATHEMATICS, 2013, 313 (03) : 301 - 311
  • [46] List Colouring of Graphs Using a Genetic Algorithm
    Khandelwal, Aditi
    Jain, Pallavi
    Saran, Gur
    SMART COMPUTING AND INFORMATICS, 2018, 77 : 573 - 581
  • [47] List colouring of graphs and generalized Dyck paths
    Xu, Rongxing
    Yeh, Yeong-Nan
    Zhu, Xuding
    DISCRETE MATHEMATICS, 2018, 341 (03) : 810 - 819
  • [48] List 4-colouring of planar graphs
    Zhu, Xuding
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2023, 162 : 1 - 12
  • [49] Wiener index in graphs with given minimum degree and maximum degree
    Alochukwu, Alex
    Dankelmann, Peter
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2021, 23 (01)
  • [50] COLOURING PLANAR GRAPHS WITH BOUNDED MONOCHROMATIC COMPONENTS
    Glebov, A. N.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2020, 17 : 513 - 520