环(圈)的公平有向染色(Equitable oriented coloring of cycles)

《Applied Mathematics and Computation》：Equitable oriented coloring of cycles

　　

一个有向图(directed graph) →G 的有向 k-染色(oriented k-coloring)是指存在保弧同态(homomorphism) →G → →T ，其中 →T 是阶数为 k 的竞赛图(tournament)。若该染色满足任意两个色类顶点数之差不超过 1，则称为公平有向 k-染色(equitable oriented k-coloring)。对于有向图 →G ，其公平有向色数(equitable oriented chromatic number) χo=(→G ) 是使 →G 存在公平有向 k-染色的最小整数 k。对于无向图 G，χo=(G) 定义为 G 的所有定向 →G 中 χo=(→G ) 的最大值。公平有向阈值(equitable oriented threshold) χo=*(G) 是指最小的 k，使得对任意 ? ≥ k，G 均为公平有向 ?-可染(fairly oriented ?-colorable)。本文研究所有环(cycle)构成的图类 C 的公平有向色数，证明 5 ≤ χo=(C) ≤ χo=*(C) ≤ 7。

论文解读：环(Cycle)的公平有向染色(Equitable Oriented Coloring)

一、研究背景与意义

有向染色(oriented coloring)由Courcelle于1994年提出，是有向图同态理论中的核心课题：一个有向图 →G 存在有向 k-染色当且仅当存在从 →G 到某 k 阶竞赛图(tournament) →T 的保弧同态映射，其最小可能的 k 值称为有向色数(oriented chromatic number) χ_o(→G )。无向图的公平染色(equitable coloring)已有广泛研究，但将有向染色与公平性约束（各色类顶点数相差不超过 1）相结合而得到的公平有向染色(equitable oriented coloring)是较新的研究方向。Dybizbański等人率先给出了路(path)及部分小阶连通无向图的公平有向染色结果，并指出与一般有向染色不同，公平有向 k-可染并不能保证对所有更大的 k 均可公平有向 (k+1)-可染，由此引出公平有向阈值(equitable oriented threshold) χ_o=^*(G) 的概念——即最小的 k 使 G 对所有 ? ≥ k 均公平有向 ?-可染。然而，对于基本图类——环(cycle, C_n)——在任意定向下的公平有向染色性质此前尚未被系统研究。本文（发表于Applied Mathematics and Computation）旨在填补这一空白，确定所有环在任意定向下公平有向色数的上下界及公平有向阈值的上界，即证明 5 ≤ χ_o=(C) ≤ χ_o=^*(C) ≤ 7，并得到当 k ≥ 7 时任意定向的任意长环均可公平有向 k-染色。

二、主要关键技术方法

研究人员采用组合构造与分情况论证的方法。对有向环 →C_n按顶点数 n = tk + r（0 ≤ r < k）沿环上循环次序将其划分为若干连续子路(subpath)，定义有向环中有向块(block，即极大有向子路)及其类型(type, 由各块长度 b_i(→C ) 组成的序列)。通过对着色所用颜色数 k 的奇偶性分别构造引理(Lemma 3.1 与 Lemma 3.2)，将子路分配至 k 阶竞赛图 →T 的不同顶点（色类）以满足保弧条件及各类大小差 ≤ 1 的公平性要求，从而证明 k ≥ 7（含奇偶两种情况）时任意定向环均可公平有向 k-染色。下界 5 由具体反例或已知有向色数结果结合公平性约束导出。

三、研究结果

Preliminaries（预备知识）

研究人员定义了有向图中 X → Y 表示 ?x∈X,?y∈Y 有弧 x→y；将有向环 →C 分解为交替方向的最大有向块 B_i(→C )，块长为 b_i(→C )，环的类型记为 (b₁(→C ), …, b_s(→C ))。这些概念为后续对有向环结构的分类讨论提供基础。

Proof of Theorem 1.2（定理1.2的证明）

定理1.2陈述：对任意 k ≥ 7，任意定向的任意环均为公平有向 k-可染(equitably oriented k-colorable)。证明中将环顶点按循环序 v₁,…,v_n分割为 t 段长度为 k 的连续子路 →P⁽ⁱ⁾= (v_(i?1)k+1, …, v_ik)（i=1,…,t），若余数 r > 0 则最后一段 →P^(t+1)= (v_tk+1, …, v_n)。在此基础上分奇偶情形给出两个引理：

• •
  Lemma 3.1：对奇数 k ≥ 7，任意定向环 →C_n可公平有向 k-染色。
• •
  （对应偶数情形引理）：对偶数 k ≥ 8（或 k ≥ 7 含偶数情况之合并结论），同理可构造公平有向 k-染色。
  综合两引理得证 Theorem 1.2，进而推出公平有向阈值 χ_o=^*(C) ≤ 7。结合已有下界结果得 5 ≤ χ_o=(C) ≤ χ_o=^*(C) ≤ 7。

四、总结与讨论

本文将有向染色与公平划分条件相结合，首次系统研究了环类图在所有可能定向下的公平有向染色性质。研究人员证明了对环图类 C，其公平有向色数 χ_o=(C) 满足 5 ≤ χ_o=(C) ≤ 7，公平有向阈值 χ_o=^*(C) 满足 χ_o=^*(C) ≤ 7，且对任意 k ≥ 7 任意定向的任意环均可实现公平有向 k-染色。此结论将 Dybizbański 等对路的公平有向染色结果推广至环，缩小了公平有向色数与公平有向阈值的未知区间（精确确定 χ_o=(C) 与 χ_o=^*(C) 是否为 5、6 或 7 尚待进一步研究），为有向图公平染色的理论体系提供了重要的图类特例与构造性证明框架。

Main Conclusion (Translated):

对于环(cycle)全体构成的图类 C，其公平有向色数(equitable oriented chromatic number) χ_o=(C) 与公平有向阈值(equitable oriented threshold) χ_o=^*(C) 满足 5 ≤ χ_o=(C) ≤ χ_o=^*(C) ≤ 7；特别地，对任意整数 k ≥ 7，无论环取何种定向(direction/orientation)，该有向环均可进行公平有向 k-染色(equitably oriented k-colored)。