跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

We prove that every graph GG whose edge set is the union of rr forests has list packing number at most 2r2^r. This means that for all k≥2rk\ge 2^r and every list-assignment LL with lists of size kk, the graph GG admits kk disjoint proper LL-colourings. While for large rr this bound is far from optimal, for r∈{1,2}r\in\{1,2\} it is sharp. As a direct corollary of the case r=2r=2, we obtain that every triangle-free planar graph has list packing number at most 44, 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=3r=3, we obtain a short alternative proof that every K5K_5-minor-free (and hence every planar) graph has list-packing number at most 88, 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)

AI 论文解读

基于摘要 · 非全文审阅

作者证明边集可分解为 r 个森林的图的列表打包数至多 2^r,并由此改进无三角形平面图等图类的列表打包上界。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-19 02:01 · 最新观测版本

List packing for graphs with small arboricity

We prove that every graph GG whose edge set is the union of rr forests has list packing number at most 2r2^r. This means that for all k≥2rk\ge 2^r and every list-assignment LL with lists of size kk, the graph GG admits kk disjoint proper LL-colourings. While for large rr this bound is far from optimal, for r∈{1,2}r\in\{1,2\} it is sharp. As a direct corollary of the case r=2r=2, we obtain that every triangle-free planar graph has list packing number at most 44, 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=3r=3, we obtain a short alternative proof that every K5K_5-minor-free (and hence every planar) graph has list-packing number at most 88, matching the state of the art. All results above also hold for the stronger notion of correspondence packing.

查看此版本解读 →查看此版本原文 ↗