← 研踪 PaperTrailarXiv:2611.24832 · v1
List packing for graphs with small arboricity
小树性图的列表打包
首次提交 2026-11-19 02:01
版本更新 2026-11-19 02:01
雷达观测 2026-11-19 15:04
摘要
We prove that every graph whose edge set is the union of forests has list packing number at most . This means that for all and every list-assignment with lists of size , the graph admits disjoint proper -colourings. While for large this bound is far from optimal, for it is sharp. As a direct corollary of the case , we obtain that every triangle-free planar graph has list packing number at most , 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 , we obtain a short alternative proof that every -minor-free (and hence every planar) graph has list-packing number at most , matching the state of the art. All results above also hold for the stronger notion of correspondence packing.
作者备注:10 pages (of which 2 for the main proofs)
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-19 02:01 · 最新观测版本
List packing for graphs with small arboricity
We prove that every graph whose edge set is the union of forests has list packing number at most . This means that for all and every list-assignment with lists of size , the graph admits disjoint proper -colourings. While for large this bound is far from optimal, for it is sharp. As a direct corollary of the case , we obtain that every triangle-free planar graph has list packing number at most , 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 , we obtain a short alternative proof that every -minor-free (and hence every planar) graph has list-packing number at most , matching the state of the art. All results above also hold for the stronger notion of correspondence packing.
查看此版本解读 →查看此版本原文 ↗