Circular chromatic index of small graphs

该论文通过系统确定最大度为 4、5、6 的小规模图及多重图的循环色指数并构造特定无穷族图，否定了关于循环色指数在 $\Delta+1$ 下方不存在图的边连通性变体“上间隙猜想”。

要点

这篇论文就像是一群数学家在**“给图的边涂色”的游戏中，试图寻找“最完美的涂色方案”**，并在这个过程中发现了一些令人惊讶的“禁区”和“新大陆”。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成一场**“交通信号灯调度大赛”**。

1. 背景故事：什么是“圆形边着色”？

想象你是一家大型停车场的管理员（或者是一个复杂的交通网络）。

• 图（Graph）：就是停车场的车道网络，顶点是路口，边是连接路口的车道。
• 最大度数（$\Delta$）：就是某个路口最多有多少条车道汇聚在一起。比如 $\Delta=4$，意味着这个路口有 4 条路。
• 传统的涂色（普通着色）：你给每条车道分配一个颜色（比如红、黄、蓝）。规则是：同一个路口汇聚的所有车道，颜色必须完全不同。如果路口有 4 条路，你至少需要 4 种颜色。
• 圆形涂色（Circular Coloring）：这是这篇论文研究的“升级版”。想象颜色不是离散的（红、黄、蓝），而是一个连续的色环（像彩虹一样，从 0 到 10 连续变化）。
  • 规则变成了：同一个路口的两条车道，它们的颜色在色环上的距离必须足够远（至少是 1 个单位）。
  • 目标：我们要找到这个色环的最小周长（记为 $\chi'_c$）。周长越小，说明我们的调度方案越“紧凑”，效率越高。

2. 核心发现：那些“消失”的颜色区间

数学家们发现，对于某些复杂的路网（$\Delta \ge 4$），色环的周长似乎有一些**“禁区”**。

• 常识：如果路口有 4 条路，你至少需要 4 种颜色。如果路很乱，可能需要 5 种。
• 猜想（上间隙猜想）：以前大家猜测，在“刚好需要 5 种颜色”和“稍微少一点点（比如 4.8 种）”之间，可能存在一个巨大的空白区。也就是说，可能不存在任何路网，其所需的色环周长正好是 4.8。就像你只能买整数的苹果，或者只能买 4 个或 5 个，买不到 4.8 个。

这篇论文的结论是：这个猜想是错的！
作者通过超级计算机，像“地毯式搜索”一样，检查了成千上万个小规模的路网。他们发现：

1. 确实存在很多路网，它们的“完美色环周长”就在 4.8、4.75 等这些“禁区”里。
2. 他们不仅找到了几个孤立的例子，还发明了一套方法，制造出了无限多种这样的路网。

3. 他们是怎么做到的？（简单的比喻）

作者就像是在玩**“乐高积木”**。

• 寻找“种子”：他们先在计算机里穷举所有的小路网（比如只有 10 个路口的小图），找到了几个特殊的“种子”图。这些种子图非常神奇，它们的涂色难度正好卡在那些“禁区”数值上（比如正好是 $4 + 3/4$）。
• 无限复制与拼接：一旦找到了一个完美的“种子”，他们就用一种**“环形拼接法”**：
  • 想象把很多个“种子”图排成一个圆圈。
  • 把前一个图的尾巴和后一个图的头连起来。
  • 通过巧妙的数学技巧，证明这样连起来的大图，依然保持着那个“完美”的涂色难度。
• 结果：只要有一个“种子”，就能造出无限多个更大、更复杂的“怪物”路网，它们都拥有那些曾经被认为“不存在”的涂色数值。

4. 为什么这很重要？

• 打破了“规则”：以前大家以为，随着路网变复杂，涂色难度会平滑地增加，中间会有断层。这篇论文证明，断层是不存在的，那些看似不可能的数值（比如 $4.75$）是真实存在的。
• 揭示了复杂性：对于简单的路口（3 条路），规则很清晰。但对于稍微复杂一点的路口（4 条、5 条、6 条路），情况变得非常混乱和不可预测。就像你从简单的二维平面跳到了复杂的三维迷宫，直觉往往不管用了。
• 计算的力量：这篇论文展示了计算机暴力搜索在数学研究中的巨大威力。面对人类无法凭直觉推导的复杂情况，计算机可以像蚂蚁搬家一样，遍历所有可能性，找到那些隐藏的规律。

5. 总结：这篇论文讲了什么？

简单来说，这篇论文就像是在说：

“我们以为在‘需要 5 种颜色’和‘需要 4 种多一点’之间有一条无法跨越的鸿沟。但通过仔细检查成千上万个小模型，我们发现鸿沟里其实藏着无数个小岛。我们还学会了如何把这些小岛连成一座无限长的桥。这告诉我们，数学世界的颜色分布比我们想象的要丰富和混乱得多。”

一句话概括：作者利用计算机穷举和巧妙的构造法，证明了在图的边着色问题中，那些曾经被认为“不存在”的数值其实是真实存在的，并推翻了关于这些数值分布的旧猜想。

技术摘要

这是一份关于论文《Circular chromatic index of small graphs》（小图的圆色指数）的详细技术总结。该论文由 Ján Mazák 和 Filip Zrubák 撰写，主要研究了最大度 $\Delta \in \{4, 5, 6\}$ 的小规模图和多图的圆色指数（Circular Chromatic Index, $\chi'_c$）。

1. 研究背景与问题 (Problem)

核心概念：

• 圆色指数 $\chi'_c(G)$：定义为图 $G$ 的边圆色数。它是使得 $G$ 的线图存在圆 $r$-边着色的最小实数 $r$。圆 $r$-边着色要求相邻边的颜色在长度为 $r$ 的圆上距离至少为 1。
• 已知结论：对于最大度 $\Delta \le 2$ 的图，情况已完全清楚。对于 $\Delta = 3$，大部分基础问题已解决。
• 主要未解问题：
  1. 上间隙猜想 (Upper Gap Conjecture)：对于整数 $k \ge 4$，是否存在图 $G$ 使得 $\chi'_c(G) \in [k + 1 - 1/k, k + 1]$？目前的证据表明，在 $\Delta+1$ 附近可能存在“间隙”，即某些值无法取到。
  2. 值域结构：$\chi'_c$ 的可能取值集合结构尚不完全清楚。特别是对于 $\Delta > 3$，是否存在大量例外图（即 $\chi'_c = \Delta + 1$ 的图）阻碍了猜想的证明。
  3. 临界性：研究重点在于 $\chi'_c$-临界图（即任何真子图的 $\chi'_c$ 都严格小于原图），因为非临界图的性质通常由子图决定，缺乏普遍意义。

本文目标：
系统地确定 $\Delta \in \{4, 5, 6\}$ 的小规模图和多图的 $\chi'_c$ 值，构建具有特定 $\chi'_c$ 值的无限图族，并检验关于 $\chi'_c$ 接近 $\Delta+1$ 的猜想。

2. 方法论 (Methodology)

计算复杂性分析：

• 确定 $\chi'_c(G) \le r$ 是 NP-完全问题（属于 NP）。
• 确定 $\chi'_c(G) = r$ 需要证明不存在更小的 $p/q$ 着色，这属于 coNP-完全问题。作者推测该问题属于 DP-完全类。
• 挑战：与整数边着色不同，圆边着色涉及的颜色数量可能高达 $|E(G)|$，导致变量数量呈二次增长，使得 SAT 求解器在处理稍大图时面临困难。

具体计算工具与流程：

1. 图生成：使用 nauty 和 genreg 生成特定阶数（order）和最大度的所有简单图及多重图。
2. 筛选与分类：
   • 利用 CVD 启发式算法、回溯法和 SAT 求解器（如 Kissat）来识别 Vizing 第二类图（Class 2，即 $\chi' > \Delta$）。
   • 对于某些特定族（如 $\Delta=4$ 的 13 顶点多重图），优先通过子图同构（VF2 算法）剔除包含强制 $\chi'_c = \Delta+1$ 子图的图，以提高效率。
3. SAT 编码：将 $p/q$-边着色问题转化为布尔可满足性问题（SAT）。变量对应 (边, 颜色) 对。
4. 构造无限族：基于计算机搜索发现的小规模“种子”图，利用“正则化”（regularization）和“循环构造”（circular construction）技术构建无限图族。
   • 引理 1：提供了一种从具有两个度为 1 的顶点的连通图 $H$ 构造无限个 $\Delta$-正则 2-边连通图 $G$ 的方法，且保持 $\chi'_c(G) = \chi'_c(H)$。

3. 主要贡献与结果 (Key Contributions & Results)

A. 计算数据概览

作者对 $\Delta \in \{4, 5, 6\}$ 的图进行了 exhaustive search（穷举搜索），统计了不同阶数下具有 $\chi' > \Delta$ 的图的数量及其 $\chi'_c$ 的取值。

• 发现模式：
  • 特定分母的值不会在理论允许的最小阶数立即出现，通常需要更多顶点。
  • 对于固定分母，分子较大的分数通常出现在更大阶数的图中。
  • 特定分数通常先出现在多重图中，随后才出现在简单图中。
• 数据表：论文提供了详细的表格（Table 1-9），列出了不同阶数下 $\chi'_c$ 的取值分布（如 $9/2, 5, 14/3, 17/4$ 等）。

B. 无限图族构造 (Infinite Families)

作者构建了多个具有特定 $\chi'_c$ 值的无限图族，这些值位于 $\Delta + 1/2$ 到 $\Delta + 1$ 之间，反驳了某些关于“上间隙”的变体猜想：

1. $\Delta = 6$:
   • 存在无限多个 2-连通 6-正则图，$\chi'_c = 7$ ($\Delta+1$)。
   • 存在无限多个图，$\chi'_c = 6 + 2/3$。
2. $\Delta = 5$:
   • 存在无限多个 2-连通 5-正则图，$\chi'_c = 6$ ($\Delta+1$)。
   • 存在无限多个多重图，$\chi'_c = 5 + 3/4$。
   • 存在无限多个 2-连通图，$\chi'_c = 5 + 2/3$。
3. $\Delta = 4$:
   • 存在无限多个 2-连通 4-正则图，$\chi'_c = 5$ ($\Delta+1$)。
   • 存在无限多个 4-连通 4-正则图，$\chi'_c = 9/2$ ($\Delta+1/2$)。
   • 存在无限多个多重图，$\chi'_c = 4 + 3/4$ 和 $4 + 2/3$。

C. 对“上间隙猜想”的证伪与修正

• 反驳：论文发现大量 $\chi'_c = \Delta + 1$ 的图（包括 4-连通图），这表明简单的边连通性假设（如 2-边连通或 $\Delta$-边连通）不足以排除 $\chi'_c = \Delta + 1$ 的情况。
• 具体反例：
  • 对于 $\Delta=4$，存在 4-连通图（如 $C_{2n+1}(1, 2)$ 对于 $n \ge 6$）具有 $\chi'_c = 9/2$。
  • 证明了 $C_{2n+1}(1, 2)$ 的 $\chi'_c$ 下界为 $4.5$，且对于$n \ge 6$上界也是$4.5$。
• 新发现值：发现了 $\Delta=4$ 时 $\chi'_c = 23/5$ 的多重图，这是首个已知的大于 $\Delta + 1/2$ 且形式不为 $\Delta + 1 - 1/t$ 的值。

D. 理论证明

• 引理 2 & 3：通过局部子图分析（Subgraph H），证明了对于 circulant 图 $C_{2n+1}(1, 2)$，若 $\chi'_c < 4.5$ 会导致矛盾，从而确立了下界。
• 引理 4：通过构造具体的 $(9, 2)$-边着色方案，证明了 $n \ge 6$ 时 $C_{2n+1}(1, 2)$ 的上界为 $4.5$。

4. 意义与影响 (Significance)

1. 挑战现有猜想：论文通过构建大量 $\chi'_c = \Delta + 1$ 的图（包括高连通性图），表明“上间隙猜想”的简单变体（如基于边连通性的排除条件）是不成立的。这迫使研究者寻找更精细的图结构特征来区分 $\chi'_c$ 的值。
2. 填补数据空白：提供了 $\Delta \in \{4, 5, 6\}$ 小图的详尽数据，揭示了 $\chi'_c$ 取值分布的复杂性和非均匀性（例如分母出现的滞后性）。
3. 构造方法创新：提出了一种基于“种子图”和循环连接构造无限 $\chi'_c$-临界（或接近临界）图族的方法，为未来寻找更多反例或验证猜想提供了工具。
4. 计算极限探索：指出了当前 SAT 求解器在处理圆色指数问题时的计算瓶颈（特别是 $\Delta \ge 7$ 时），并解释了为何 $\Delta=7$ 以上的上间隙猜想验证目前不可行。
5. 提出新问题：文末提出了 7 个开放问题，包括关于 $\chi'_c$ 临界图的数量、简单图与多重图取值差异、以及高连通正则图的最小 $\chi'_c$ 等，为后续研究指明了方向。

5. 结论

该论文通过系统的计算实验和理论构造，极大地扩展了对最大度 $\Delta \in \{4, 5, 6\}$ 图圆色指数的理解。研究结果表明，$\chi'_c$ 的取值结构比预想的更为复杂，且在 $\Delta+1$ 附近存在大量例外图，这使得证明“上间隙猜想”变得极具挑战性。作者不仅提供了丰富的数据支持，还构建了具有特定性质的无限图族，为图论中的着色理论提供了新的视角和反例。