2025-11-22T09:52:16.162568

On acyclic b-chromatic number of cubic graphs

Anholcer, Cichacz, Peterin

Let $G$ be a graph. An acyclic $k$-coloring of $G$ is a map $c:V(G)\rightarrow \{1,\dots,k\}$ such that $c(u)\neq c(v)$ for any $uv\in E(G)$ and the subgraph induced by the vertices of any two colors $i,j\in \{1,\dots,k\}$ is a forest. If every vertex $v$ of a color class $V_i$ misses a color $\ell_v\in\{1,\dots,k\}$ in its closed neighborhood, then every $v\in V_i$ can be recolored with $\ell_v$ and we obtain a $(k-1)$-coloring of $G$. If a new coloring $c'$ is also acyclic, then such a recoloring is an acyclic recoloring step and $c'$ is in relation $\triangleleft_a$ with $c$. The acyclic b-chromatic number $A_b(G)$ of $G$ is the maximum number of colors in an acyclic coloring where no acyclic recoloring step is possible. Equivalently, it is the maximum number of colors in a minimum element of the transitive closure of $\triangleleft_a$. In this paper, we consider $A_b(G)$ of cubic graphs.

academic

On acyclic b-chromatic number of cubic graphs

基本信息

论文ID: 2511.01532
标题: On acyclic b-chromatic number of cubic graphs
作者: Marcin Anholcer (Poznań University of Economics and Business), Sylwia Cichacz (AGH University), Iztok Peterin (University of Maribor)
分类: math.CO (组合数学), cs.DM (离散数学)
发表时间: 2025年11月4日
论文链接: https://arxiv.org/abs/2511.01532

摘要

本文研究图的无圈b-色数（acyclic b-chromatic number）在三次图（cubic graphs）上的性质。无圈k-着色要求相邻顶点颜色不同，且任意两种颜色诱导的子图是森林。无圈b-色数 $A_b(G)$ 是在无法进行无圈重着色步骤的无圈着色中使用的最大颜色数。本文证明了除一个例外外，所有三次图的无圈b-色数为4或5，并详细研究了广义Petersen图和(0,j)-棱柱图的无圈b-色数。

研究背景与动机

研究问题

本文研究图的无圈b-色数问题，这是结合了两个经典图着色概念的新问题：

b-着色（b-coloring）：由Irving和Manlove于1999年提出，通过迭代重着色步骤从平凡着色出发，最大化最终着色使用的颜色数
无圈着色（acyclic coloring）：由Grünbaum提出，要求任意两种颜色诱导的子图是森林（无圈）

重要性

该问题具有以下重要意义：

理论价值：连接了两个重要的图着色变体，形成新的图不变量
正则图研究：对于d-正则图，b-色数是否等于d+1是核心问题。三次图（3-正则图）是最简单的非平凡情况
组合优化：为图着色问题提供新的优化视角

现有研究局限

对于b-色数φ(G)，已知所有三次图除4个例外外都有φ(G)=4（Jakovac和Klavžar，2010）
对于无圈b-色数 $A_b(G)$ ，之前的工作3只建立了基本理论框架，缺乏对具体图类的系统研究
$A_b(G)$ 与其他图参数（如 $\Delta(G)$ , φ(G), A(G)）的关系尚不清楚

研究动机

作者旨在系统研究三次图的无圈b-色数，这是向正则图一般结果迈进的重要一步。三次图作为最简单的非平凡正则图类，其研究结果可为更一般情况提供洞察。

核心贡献

建立三次图无圈b-色数的基本范围：证明除棱柱 $K_2\Box K_3$ 外，所有三次图G满足 $4 \leq A_b(G) \leq 5$
揭示与b-色数的本质差异：证明存在无穷多个三次图G满足 $A_b(G)=4$ ，这与b-色数的有限性结果形成鲜明对比
完全确定特殊图类的无圈b-色数：
- 广义Petersen图G(n,k)：当k≥3且n足够大时， $A_b(G(n,k))=5$
- 棱柱G(n,1)：对n≥4， $A_b(G(n,1))=4$ ； $A_b(K_2\Box K_3)=3$
- (0,j)-棱柱：当j>0且n≥5(j+2)时， $A_b(\text{Pr}_n(0,j))=5$
构造性证明方法：提供了显式的5-着色构造，展示了无圈b-顶点的两种类型（A型和B型）
提出开放问题：包括计算复杂性、snark图的无圈b-色数等

方法详解

任务定义

无圈着色：图G的k-着色 $c: V(G) \to [k]$ 称为无圈着色，如果：

相邻顶点颜色不同（正常着色条件）
对任意 $i,j \in [k]$ ，颜色i和j诱导的子图 $G[V_i \cup V_j]$ 是森林

无圈重着色步骤：对于颜色类 $V_i$ ，如果每个顶点 $v \in V_i$ 在其闭邻域中缺失某颜色 $\ell_v$ ，且将所有 $v \in V_i$ 重着色为 $\ell_v$ 后仍保持无圈着色，则称为一次无圈重着色步骤。

无圈b-色数 $A_b(G)$ ：从平凡着色（每个顶点独立颜色）开始，通过无圈重着色步骤迭代，最终无法继续重着色时的最大颜色数。

无圈b-顶点：在无法进行无圈重着色的着色中，如果顶点v的任何重着色都会产生双色圈，则v是无圈b-顶点。

理论框架

关键性质：

对于三次图， $A_b(G) \leq 5$ （由一般上界 $A_b(G) \leq \frac{1}{2}\Delta(G)^2 + 1$ 得出）
$A(G) \leq A_b(G)$ （无圈色数是下界）
无圈b-顶点分类：
- A型：三个邻居同色
- B型：邻居有两种颜色

阻塞圈（blocking cycle）：对于无圈b-顶点v（颜色i），如果颜色j不在其闭邻域中，使得v不能重着色为j的最短双色圈称为 $j_v$ -圈。

主要技术方法

1. 无圈着色的可达性（Theorem 3.2）

核心思想：任何三次图的4-着色都可以通过局部调整消除所有双色圈。

算法流程：

输入：三次图G的4-着色c（可能有双色圈）
输出：G的无圈4-着色

while 存在双色圈C do:
    设C = v₁v₂...vₖv₁，颜色交替为1和2
    设uᵢ为vᵢ的第三个邻居
    
    Case 1: 存在uⱼ使得c(uⱼ) ∈ {1,2}
        根据uⱼ₋₁和uⱼ₊₁的颜色，重着色vⱼ为颜色3或4
        
    Case 2: 所有uᵢ的颜色都不在{1,2}中
        假设c(u₂)=3，重着色v₂为4
        如果产生新双色圈，进一步调整v₁,v₂,v₃的颜色

关键性质：每次操作严格减少双色圈数量，保证算法终止。

2. 三次图下界构造（Theorem 3.3）

策略：利用Jakovac和Klavžar关于b-色数的证明框架，修正其中的双色圈。

步骤：

在最短圈C上开始着色
扩展到C附近的顶点，确保每种颜色有b-顶点
对于18中出现双色圈的四个配置（见Figure 3），提供修正着色
其余部分使用贪心着色，利用Theorem 3.2消除双色圈

3. 上界5的紧性证明

构造无穷多个 $A_b(G)=4$ 的三次图（Theorem 3.5）：

从立方树T构造三次图C(T)：

将T的每个内部顶点v（度为3）替换为三角形abc
在T的每个叶子处连接子图 $H_3$ 的拷贝

关键引理3.4： $H_3$ 中度为2的顶点w不能是5-着色中的无圈b-顶点。

证明思路：

w作为割点，其闭邻域最多4种颜色
若w是无圈b-顶点，必须是B型（邻居同色）
但 $H_3$ 中w的两个邻居相邻，矛盾

因此C(T)无法有5-着色的无圈b-着色，而4-着色可构造。

4. 广义Petersen图的5-着色构造（Theorem 4.1）

条件： $k \geq 3$ ， $n \geq 5(2k + (-1)^k)$

构造策略：设计局部配置，使得特定顶点 $x_j$ 成为B型无圈b-顶点。

奇数k的情况：

构造两个圈 $C^1_j$ 和 $C^2_j$ 包含 $x_j$
$C^1_j$ ：长度 $k+2$ ，使用颜色 $c^0_j, c^1_j, c^3_j$
$C^2_j$ ：长度 $2k+2$ ，使用颜色 $c^0_j, c^2_j, c^3_j$
$x_j$ 的邻居用 $c^3_j$ 和 $c^4_j$ 着色
$C^1_j$ 是 $(c^1_j)_{x_j}$ -圈， $C^2_j$ 是 $(c^2_j)_{x_j}$ -圈

重复模式：每隔 $2k-1$ 个位置放置一个无圈b-顶点，通过颜色置换保证一致性。

偶数k的情况：类似构造，间隔为 $2k+1$ 。

实验设置

本文为纯理论数学论文，不涉及计算实验。所有结果通过严格的数学证明获得。

研究对象

三次图一般类：所有顶点度数为3的图
特殊图类：
- Petersen图P = G(5,2)
- 棱柱 $K_2\Box K_3$ , $K_{3,3}$ , $G_1$
- 广义Petersen图G(n,k)
- (0,j)-棱柱 $\text{Pr}_n(0,j)$
- 立方树构造的图C(T)

证明技术

构造性证明：显式给出着色方案
反证法：证明某些着色不存在
归纳法：消除双色圈的算法
配置分析：穷举局部结构的可能性

实验结果

主要结果

结果1：三次图的基本范围（Theorem 3.3）

定理：对于每个三次图G，除了 $K_2\Box K_3$ 外，有 $A_b(G) \geq 4$ 。此外， $A_b(K_2\Box K_3) = 3$ 。

意义：结合上界 $A_b(G) \leq 5$ ，确定了三次图无圈b-色数的可能值为{3,4,5}。

结果2：与b-色数的对比（Corollary 3.6）

定理：满足 $A_b(G) < 5$ 的三次图数量是无穷的。

对比：b-色数φ(G)<4的三次图只有4个（Theorem 3.1）。

具体例子：对于任何立方树T， $A_b(C(T)) = 4$ （Theorem 3.5）。由于立方树有无穷多个，结论成立。

结果3：广义Petersen图（Theorem 4.1, 4.2）

图类	条件	$A_b(G)$
G(5,2) (Petersen图)	-	4
G(n,1) (棱柱)	n=3	3
G(n,1)	n≥4	4
G(n,k)	k≥3, n≥5(2k+(-1)^k)	5

关键发现：

Petersen图无法达到5，因为无圈b-顶点的存在性约束
普通棱柱（k=1）最多达到4
参数k≥3且n足够大时可以达到上界5

结果4：(0,j)-棱柱（Theorem 5.1）

定理：如果 $j > 0$ 且 $n \geq 5(j+2)$ ，则 $A_b(\text{Pr}_n(0,j)) = 5$ 。

构造要点：

在顶点 $v^1_{2i+1}$ 处设计局部配置
利用两个圈 $C^1_k$ 和 $C^2_k$ 阻塞特定颜色
每隔 $j+2$ 个位置重复配置

技术发现

发现1：无圈b-顶点的类型分析

对于三次图中的非b-顶点：

A型（三邻居同色）：较难构造，需要特殊结构
B型（邻居两种颜色）：更常见，通过双色圈阻塞实现

发现2：局部配置的可重复性

通过精心设计的颜色置换方案，可以将局部无圈b-着色配置周期性重复，构造任意大的图。

发现3：割点的限制作用

Lemma 3.4揭示：度为2的割点（如 $H_3$ 中的w）无法成为5-着色中的无圈b-顶点，这是构造 $A_b(G)=4$ 图族的关键。

案例分析

案例1：Petersen图的4-着色（Figure 2左图）

使用颜色{1,2,3,4}
黑色顶点为无圈b-顶点
颜色1的顶点是A型（三邻居同色为2）
其他颜色的顶点是B型

案例2： $C(K_{1,3})$ 的构造（Figure 4）

中心三角形用颜色{1,2,3}
三个 $H_3$ 拷贝用颜色{1,2,3,4}
每个 $H_3$ 中有B型无圈b-顶点
整体达到 $A_b=4$ 但无法达到5

结论与讨论

主要结论

基本范围确定：除 $K_2\Box K_3$ 外，所有三次图G满足 $4 \leq A_b(G) \leq 5$
与b-色数的本质差异：
- b-色数：只有4个三次图φ(G)<4（有限性）
- 无圈b-色数：无穷多个三次图 $A_b(G)=4$ （无限性）
特殊图类的完整刻画：
- 广义Petersen图：参数充分大时达到上界5
- 棱柱：最多达到4
- 立方树构造：恰好为4
构造技术：提供了系统的5-着色构造方法，基于局部配置的周期重复

局限性

未完全解决的问题：
- 对于一般三次图，何时 $A_b(G)=4$ 、何时 $A_b(G)=5$ 的完整刻画仍未知
- 广义Petersen图G(n,k)在n较小或k=2时的情况未完全覆盖
方法局限：
- 构造方法依赖于图的特殊结构（如对称性）
- 对于不规则或复杂结构的三次图缺乏通用判定方法
计算复杂性未知：判定三次图 $A_b(G)=4$ 还是5的计算复杂性仍是开放问题

未来方向

论文提出三个开放问题：

Problem 6.1（计算复杂性）：判定三次图G满足 $A_b(G)=4$ 还是 $A_b(G)=5$ 的计算复杂性是什么？

Problem 6.2（snark图）：snark（无3-边着色的三次图）的无圈b-色数是多少？

Problem 6.3（无圈立方图）：找到更多"无圈立方图"（每个顶点的无圈度也为3）的图类。

Conjecture 6.4（围长与b-色数关系）：如果 $g(G) > 2\phi(G)$ ，则 $A_b(G) \geq \phi(G)$ 。

推测：围长足够大时，b-着色自然是无圈的，无圈b-色数应与b-色数相等。

深度评价

优点

理论完整性：
- 系统建立了三次图无圈b-色数的基本理论框架
- 证明严谨，逻辑清晰，每个定理都有完整证明
- 巧妙利用了已有的b-色数结果（Jakovac & Klavžar）
方法创新性：
- 局部配置设计：通过精心设计的双色圈阻塞机制实现无圈b-顶点
- 颜色置换技巧：使局部配置可以周期重复，构造任意大的图
- 分类讨论：A型和B型无圈b-顶点的分类简化了分析
结果深刻性：
- 揭示本质差异：证明 $A_b(G)$ 与φ(G)在三次图上的行为根本不同（有限vs无限）
- 构造性证明：不仅证明存在性，还给出显式构造
- 特殊图类完整刻画：对多个重要图类给出精确值
写作清晰度：
- 大量图示（Figures 1-11）直观展示着色方案
- 逐步引入概念，从简单到复杂
- 明确区分不同情况（奇偶k、不同参数范围）

不足

覆盖范围：
- 对于广义Petersen图G(n,k)，当k=2或n较小时的情况未完全解决
- 缺乏对一般三次图的充要条件刻画
- 没有讨论其他重要三次图类（如Cayley图、笼图）
算法角度：
- 未提供判定算法或启发式方法
- 计算复杂性完全开放
- 缺乏实际计算的讨论（虽然这是理论论文）
上下界的gap：
- 对于许多三次图，仍不知道 $A_b(G)$ 是4还是5
- 缺乏易于验证的充分条件
与其他参数的关系：
- 除了与φ(G)的对比，未深入探讨与围长g(G)、色数χ(G)、无圈色数A(G)的关系
- Conjecture 6.4虽然提出但未验证

影响力

理论贡献：
- 为正则图的无圈b-色数研究奠定基础
- 提供的构造技术可能适用于其他正则图类
- 揭示的有限性vs无限性差异是重要理论洞察
研究方向：
- 开辟了三次图及正则图着色理论的新研究方向
- 提出的开放问题具有明确的研究价值
- 可能激发对snark、笼图等特殊三次图的研究
实用价值：
- 作为纯理论研究，直接应用有限
- 但图着色在调度、频道分配、寄存器分配等领域有应用背景
- 无圈约束在某些应用中有实际意义（避免死锁、循环依赖）
可复现性：
- 所有证明完整且可验证
- 构造方法明确，可以手工验证小图的情况
- 适合作为进一步研究的起点

适用场景

理论研究：
- 图着色理论的研究者
- 正则图性质的研究
- 组合优化中的着色问题
潜在应用：
- 网络设计（避免循环依赖）
- 调度问题（任务分组且避免冲突圈）
- 编译器优化（寄存器分配）
教学价值：
- 展示了构造性证明的技巧
- 组合数学和图论的良好案例
- 局部到全局构造的范例

参考文献

本文引用了24篇参考文献，关键文献包括：

17 Irving & Manlove (1999)：b-色数的原始论文
18 Jakovac & Klavžar (2010)：三次图b-色数的关键结果
3 Anholcer, Cichacz, Peterin (2023)：无圈b-色数的引入
1 Alon, McDiarmid, Reed (1991)：无圈着色的经典上界
5 Borodin (1979)：平面图无圈着色
21 Kratochvíl, Tuza, Voigt (2002)：b-色数的复杂性

总体评价：这是一篇高质量的理论数学论文，系统研究了三次图的无圈b-色数问题。论文证明严谨，结果深刻，特别是揭示了无圈b-色数与b-色数在三次图上的本质差异。虽然仍有许多开放问题，但本文为该领域的进一步研究奠定了坚实基础。推荐给图论和组合优化研究者阅读。