2025-11-10T03:06:56.403525

List Packing and Correspondence Packing of Planar Graphs

Cranston, Smith-Roberge

For a graph $G$ and a list assignment $L$ with $|L(v)|=k$ for all $v$, an $L$-packing consists of $L$-colorings $Ï_1,\cdots,Ï_k$ such that $Ï_i(v)\neÏ_j(v)$ for all $v$ and all distinct $i,j\in\{1,\ldots,k\}$. Let $Ï^{\star}_{\ell}(G)$ denote the smallest $k$ such that $G$ has an $L$-packing for every $L$ with $|L(v)|=k$ for all $v$. Let $\mathcal{P}_k$ denote the set of all planar graphs with girth at least $k$. We show that (i) $Ï^{\star}_{\ell}(G)\le 8$ for all $G\in \mathcal{P}_3$ and (ii) $Ï^{\star}_{\ell}(G)\le 5$ for all $G\in \mathcal{P}_4$ and (iii) $Ï^{\star}_{\ell}(G)\le 4$ for all $G\in \mathcal{P}_5$. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also construct outerplanar graphs $G$ such that $Ï^{\star}_{\ell}(G)=4$, which matches the known upper bound $Ï^{\star}_{\ell}(G)\le 4$ for all outerplanar graphs. Finally, we consider the analogue of $Ï^{\star}_{\ell}$ for correspondence coloring, $Ï^{\star}_c$. In fact, all bounds stated above for $Ï^{\star}_{\ell}$ also hold for $Ï^{\star}_c$.

academic

List Packing and Correspondence Packing of Planar Graphs

基本信息

论文ID: 2401.01332
标题: List Packing and Correspondence Packing of Planar Graphs
作者: Daniel W. Cranston (Virginia Commonwealth University), Evelyne Smith-Roberge (Georgia Tech)
分类: math.CO (组合数学)
发表时间: 2024年12月6日 (arXiv第3版)
论文链接: https://arxiv.org/abs/2401.01332

摘要

本文研究平面图的列表打包(list packing)和对应打包(correspondence packing)问题。对于图 $G$ 和列表分配 $L$ ，其中 $|L(v)|=k$ 对所有顶点 $v$ 成立，一个 $L$ -打包包含 $L$ -着色 $\phi_1,\cdots,\phi_k$ 使得对所有 $v$ 和不同的 $i,j\in\{1,\ldots,k\}$ 都有 $\phi_i(v)\neq\phi_j(v)$ 。令 $\chi^{\star}_{\ell}(G)$ 表示使得 $G$ 对每个 $|L(v)|=k$ 的 $L$ 都有 $L$ -打包的最小 $k$ 值。文章证明了：(i) 对所有围长至少为3的平面图 $G$ 有 $\chi^{\star}_{\ell}(G)\leq 8$ ；(ii) 对所有围长至少为4的平面图 $G$ 有 $\chi^{\star}_{\ell}(G)\leq 5$ ；(iii) 对所有围长至少为5的平面图 $G$ 有 $\chi^{\star}_{\ell}(G)\leq 4$ 。这些结果对对应着色的类似参数 $\chi^{\star}_c$ 也成立。

研究背景与动机

核心问题：研究平面图的列表打包数和对应打包数的上界问题。列表打包是列表着色的推广，要求找到多个互不相交的列表着色。
问题重要性：
- 列表着色是图论中的经典问题，有广泛的理论和应用价值
- 打包问题是着色问题的自然推广，研究资源分配的优化
- 平面图作为重要的图类，其着色性质具有特殊的理论意义
现有局限性：
- Cambie等人在2024年的工作中证明了 $\chi^{\star}_c(G)\leq 10$ 对所有平面图 $G$ 成立
- 但这个界限相对较粗糙，需要进一步改进
- 对不同围长的平面图缺乏精细的分析
研究动机：
- 改进已知的上界，特别是Cambie等人提出的问题
- 建立围长与打包数之间的精确关系
- 为对应着色提供统一的分析框架

核心贡献

显著改进了平面图的打包数上界：将 $\chi^{\star}_c(G)\leq 10$ 改进为 $\chi^{\star}_c(G)\leq 8$
建立了围长与打包数的精确关系：
- 围长≥4： $\chi^{\star}_c(G)\leq 5$
- 围长≥5： $\chi^{\star}_c(G)\leq 4$ （最优）
提供了完全手工验证的证明：与同期工作不同，避免了计算机验证
统一处理列表打包和对应打包：所有结果对两种打包都成立
证明了围长≥5情况的最优性：通过构造例子说明界限是紧的