2025-11-16T11:46:12.516239

Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

Balaji, Khazhinsky, Liu et al.
Odd coloring is a variant of proper coloring and has received wide attention. We study the list-coloring version of this notion in this paper. We prove that if $G$ is a graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, and 6 such that no 5-cycles share an edge, then for every function $L$ that assigns each vertex of $G$ a set $L(v)$ of size 5, there exists a proper coloring that assigns each vertex $v$ of $G$ an element of $L(v)$ such that for every non-isolated vertex, some color appears an odd number of times on its neighborhood. In particular, every graph embeddable in the torus or the Klein bottle with no cycle of length 3, 4, 6, and 8 is odd 5-choosable. The number of colors in these results are optimal, and there exist graphs embeddable in those surfaces of girth 6 requiring six or seven colors.
academic

Odd list-coloring of graphs of small Euler genus with no short cycles of specific types

基本信息

  • 论文ID: 2508.15255
  • 标题: Odd list-coloring of graphs of small Euler genus with no short cycles of specific types
  • 作者: Rishi Balaji, Victoria Khazhinsky, Chun-Hung Liu, Kevin Qin
  • 分类: math.CO (组合数学)
  • 发表时间: October 14, 2025
  • 论文链接: https://arxiv.org/abs/2508.15255

摘要

本文研究图的奇着色(odd coloring)的列表着色版本。主要结果证明：如果图G可嵌入环面或Klein瓶，且不包含长度为3、4、6的圈，并且没有两个5-圈共享边，那么对于每个给每个顶点分配大小为5的颜色集合的函数L，都存在适当的着色使得每个非孤立顶点的邻域中某种颜色出现奇数次。特别地，每个可嵌入环面或Klein瓶且不包含长度为3、4、6、8的圈的图都是奇5-可选择的。研究表明这些结果中的颜色数是最优的。

研究背景与动机

问题定义

  1. 奇着色问题: 奇着色是适当着色的一个变种，要求对于每个非孤立顶点，其邻域中至少有一种颜色出现奇数次
  2. 列表着色: 每个顶点有一个可用颜色的列表，着色必须从各自的列表中选择颜色
  3. 曲面嵌入图: 研究可嵌入特定曲面(环面、Klein瓶)的图的着色性质

研究重要性

  • 奇着色概念虽然相对较新(2022年由Petruševski和Škrekovski引入)，但已引起广泛关注
  • 结合了图论中两个重要概念：曲面嵌入和受限圈结构
  • 对理解图着色理论在拓扑约束下的行为具有重要意义

现有研究局限

  • Petruševski和Škrekovski猜想每个平面图都是奇5-可着色的，但目前最好结果是奇8-可着色
  • 对于更一般曲面上的图，已知结果较少
  • 列表着色版本的奇着色研究更为稀少

核心贡献

  1. 主要定理: 证明了可嵌入环面或Klein瓶且满足特定圈条件的图是奇5-可选择的
  2. 最优性结果: 证明了所需颜色数5是最优的，存在需要6或7种颜色的反例
  3. 技术框架: 发展了更强的技术结果(Theorem 1.1的推广版本Theorem 1.3)
  4. 方法创新: 使用放电方法(discharging method)系统性地分析图的结构

方法详解

任务定义

输入: 图G，可嵌入环面或Klein瓶，满足圈长度限制条件，以及5-列表分配L 输出: 适当的L-着色，使得每个非孤立顶点的邻域中某种颜色出现奇数次 约束:

  • 无长度为3、4、6的圈
  • 无两个5-圈共享边

核心技术方法

R-长度概念

对于图G和边集R ⊆ E(G)，圈C的R-长度定义为|E(C)| + |E(C) ∩ R|。这一概念统一了原问题和推广版本的处理。

R-松弛顶点

顶点v是R-松弛的，如果：

  • deg(v)为奇数或0，或
  • v与R中的某条边相邻

主要技术定理(Theorem 1.3)

设G可嵌入环面或Klein瓶，R ⊆ E(G)。如果：

  • 无R-长度为3、4、6的圈
  • 无两个R-长度为5的圈恰好共享一条边

则对每个5-列表分配L，存在适当L-着色使得每个非R-松弛顶点的邻域中某种颜色出现奇数次。

证明策略

最小反例分析

假设存在最小反例G，通过分析其结构性质：

  1. 连通性: 证明G必须连通(Lemma 3.1)
  2. 最小度: 每个顶点度数至少为3(Lemma 3.2)
  3. 3-顶点限制: 3度顶点不能与太多R-松弛顶点相邻(Lemma 3.3)
  4. 圈结构: 详细分析3-圈、4-圈、5-圈的R-长度和相互关系

放电方法

使用经典的放电技术：

初始电荷:

  • 顶点v: ch(v) = deg(v) - 4
  • 面f: ch(f) = leng(f) - 4

放电规则(R1)-(R8):

  • (R1): (≥5)-面向相邻3-顶点发送1/2单位电荷
  • (R2)-(R6): 处理面之间的电荷转移
  • (R7): (≥5)-顶点向相邻3-面发送1/2单位电荷
  • (R8): (≥6)-顶点向满足条件的5-面发送1/3单位电荷

电荷分析

通过精细的电荷计算，证明：

  • 每个顶点和面的最终电荷非负
  • 总电荷严格为正
  • 这与欧拉公式矛盾，从而否定了反例的存在

实验设置

理论验证

本文是纯理论工作，主要通过数学证明验证结果：

  1. 构造性证明: 对满足条件的图，构造性地给出奇5-着色
  2. 反例构造: 证明颜色数5的最优性
    • 5-圈不是奇4-可着色的
    • K7的1-细分不是奇6-可着色的
    • K6的1-细分不是奇5-可着色的

技术工具

  • 欧拉公式用于曲面上图的约束
  • 放电方法的系统性应用
  • 图结构的局部分析技术

实验结果

主要结果

Theorem 1.1 (主定理)

可嵌入环面或Klein瓶且无长度3、4、6的圈并且无两个5-圈共享边的图G是奇5-可选择的。

Corollary 1.2

可嵌入环面或Klein瓶且无长度3、4、6、8的圈的图G是奇5-可选择的。

最优性

  • 颜色数5是最优的：5-圈需要5种颜色
  • 圈长度限制是必要的：存在围长6的反例需要6-7种颜色

技术结果验证

通过详细的结构分析证明了关键引理：

  • Lemma 3.5: 3-圈必须有R-长度5，且所有顶点都是R-松弛的
  • Lemma 3.16: 4-顶点不能只与4-面相邻
  • Lemma 4.11: 放电后总电荷严格为正

相关工作

奇着色研究发展

  1. 起源: Petruševski和Škrekovski (2022)引入概念并猜想平面图是奇5-可着色的
  2. 平面图结果:
    • 最初证明：奇9-可着色
    • 改进：Petr和Portier证明奇8-可着色
  3. 曲面推广: Metrebian以及Tian和Yin证明环面图是奇9-可着色的

列表着色背景

  • 列表着色是着色理论的重要分支
  • 本文首次系统研究奇着色的列表版本
  • 结合曲面嵌入和圈结构约束是新的研究方向

方法论贡献

  • 放电方法在奇着色中的应用
  • R-长度概念的引入统一了不同情况的处理
  • 为后续研究提供了技术框架

结论与讨论

主要结论

  1. 在适当的圈结构约束下，环面和Klein瓶上的图具有良好的奇列表着色性质
  2. 5种颜色足以处理这类图，且这个界是紧的
  3. 放电方法是分析此类问题的有效工具

局限性

  1. 曲面限制: 结果仅适用于欧拉亏格至多为2的曲面
  2. 圈条件: 需要排除多种短圈，条件较为严格
  3. 构造性: 证明是存在性的，未给出高效算法

未来方向

  1. 推广到更高亏格的曲面
  2. 放松圈长度的限制条件
  3. 研究算法复杂性和具体构造方法
  4. 探索其他图类的奇列表着色性质

深度评价

优点

技术创新

  1. 概念创新: R-长度和R-松弛概念的引入elegant地统一了问题的不同变种
  2. 方法严谨: 放电方法的应用非常系统和完整
  3. 结果最优: 证明了颜色数的最优性，结果是紧的

理论贡献

  1. 首次结果: 在奇列表着色领域的重要进展
  2. 技术框架: 为后续研究提供了可借鉴的方法
  3. 完整性: 从主要结果到技术细节都处理得很完善

学术价值

  1. 问题重要: 连接了图着色、拓扑图论和组合优化
  2. 结果深刻: 揭示了曲面约束对着色性质的影响
  3. 方法通用: 技术可能适用于其他相关问题

不足

技术限制

  1. 条件严格: 对圈结构的要求较为复杂，实际应用中可能限制较大
  2. 曲面局限: 仅处理了最简单的非平凡曲面情况
  3. 算法缺失: 没有给出构造奇着色的具体算法

分析深度

  1. 参数依赖: 对为什么恰好需要5种颜色的本质原因分析不够深入
  2. 结构刻画: 对满足条件的图类的结构特征刻画有限
  3. 推广性: 技术向其他问题推广的潜力需要进一步探索

影响力

理论影响

  • 为奇着色理论的发展提供了重要的技术工具和结果
  • 可能启发曲面图着色理论的新研究方向
  • 放电方法的新应用可能影响相关证明技术

实用价值

  • 虽然是纯理论结果，但可能在网络着色、频谱分配等应用中有潜在价值
  • 为算法设计提供了理论基础

可复现性

  • 证明完整且详细，技术路线清晰
  • 主要结果可以被独立验证
  • 为后续工作提供了solid的基础

适用场景

  1. 理论研究: 图着色理论、拓扑图论研究
  2. 算法设计: 需要特殊着色性质的网络问题
  3. 教学: 作为放电方法应用的经典案例
  4. 推广研究: 向其他图类或着色变种的推广

参考文献

论文引用了38篇相关文献，主要包括：

基础理论:

  • Four Color Theorem相关工作 4,5,6,34
  • 曲面图着色理论 3,18,20,22,33

奇着色研究:

  • 概念起源 32
  • 平面图结果 31,14,11
  • 曲面推广 29,36

技术方法:

  • 放电方法应用 25
  • 相关着色问题 1,2,10,12,16,17,24,26,27

总体评价: 这是一篇高质量的理论论文，在奇列表着色这一新兴领域做出了重要贡献。技术严谨，结果最优，为该领域的发展奠定了坚实基础。虽然条件较为技术性，但开辟了新的研究方向，具有重要的学术价值。