小树性图的列表打包
List packing for graphs with small arboricity
Stijn Cambie, Wouter Cames van Batenburg, Xuding Zhu
AI 速读 基于摘要
作者证明边集可分解为 r 个森林的图的列表打包数至多 2^r,并由此改进无三角形平面图等图类的列表打包上界。
math.CO · cs.DM
查看原文摘要
We prove that every graph $G$ whose edge set is the union of $r$ forests has list packing number at most $2^r$. This means that for all $k\ge 2^r$ and every list-assignment $L$ with lists of size $k$, the graph $G$ admits $k$ disjoint proper $L$-colourings. While for large $r$ this bound is far from optimal, for $r\in\{1,2\}$ it is sharp. As a direct corollary of the case $r=2$, we obtain that every triangle-free planar graph has list packing number at most $4$, thus improving upon a result of Dvořák, Masařík, Musílek and Pangrác and providing the optimal answer to a question of Dvořák, Postle and Norin on (weighted) $ε$-flexibility of such graphs. As a corollary of the case $r=3$, we obtain a short alternative proof that every $K_5$-minor-free (and hence every planar) graph has list-packing number at most $8$, matching the state of the art. All results above also hold for the stronger notion of correspondence packing.