2025-11-10T03:07:44.268793

Bounds on Coloring Trees without Rainbow Paths

Goddard, Herrman, Hughes

For a graph with colored vertices, a rainbow subgraph is one where all vertices have different colors. For graph $G$, let $c_k(G)$ denote the maximum number of different colors in a coloring without a rainbow path on $k$ vertices, and $cp_k(G)$ the maximum number of colors if the coloring is required to be proper. The parameter $c_3$ has been studied by multiple authors. We investigate these parameters for trees and $k \ge 4$. We first calculate them when $G$ is a path, and determine when the optimal coloring is unique. Then for trees $T$ of order $n$, we show that the minimum value of $c_4(T)$ and $cp_4(T)$ is $(n+2)/2$, and the trees with the minimum value of $cp_4(T)$ are the coronas. Further, the minimum value of $c_5(T)$ and $cp_5(T)$ is $(n+3)/2$ , and the trees with the minimum value of either parameter are octopuses.

academic

Bounds on Coloring Trees without Rainbow Paths

基本信息

论文ID: 2501.01302
标题: Bounds on Coloring Trees without Rainbow Paths
作者: Wayne Goddard, Tyler Herrman, Simon J. Hughes (Clemson University)
分类: math.CO (组合数学)
发表时间: 2025年1月2日
论文链接: https://arxiv.org/abs/2501.01302

摘要

对于顶点着色的图，彩虹子图是指所有顶点颜色不同的子图。对于图 $G$ ，令 $c_k(G)$ 表示不包含 $k$ 个顶点的彩虹路径的着色中不同颜色的最大数量， $cp_k(G)$ 表示在要求正常着色（相邻顶点颜色不同）条件下的最大颜色数。参数 $c_3$ 已被多位学者研究。本文研究树和 $k \geq 4$ 的情况。首先计算了当 $G$ 是路径时的这些参数，并确定了最优着色的唯一性条件。然后对于 $n$ 阶树 $T$ ，证明了 $c_4(T)$ 和 $cp_4(T)$ 的最小值为 $(n+2)/2$ ，使 $cp_4(T)$ 达到最小值的树恰好是冠图。进一步地， $c_5(T)$ 和 $cp_5(T)$ 的最小值为 $(n+3)/2$ ，使任一参数达到最小值的树是章鱼图。

研究背景与动机

研究问题：本文研究在图的顶点着色中避免彩虹路径的问题。给定图 $G$ 和正整数 $k$ ，目标是确定在不产生 $k$ 个顶点的彩虹路径（所有顶点颜色不同的路径）的前提下，最多可以使用多少种不同的颜色。
问题重要性：
- 这是反拉姆齐理论在顶点着色中的应用，具有重要的理论价值
- 与图的结构性质和着色理论密切相关
- 为理解图的色数与其结构之间的关系提供新的视角
现有研究局限性：
- 参数 $c_3$ 已被广泛研究，但 $k \geq 4$ 的情况研究较少
- 对于树这一重要图类，缺乏系统的研究
- 缺少对极值图结构的完整刻画
研究动机：填补 $k \geq 4$ 情况下树的彩虹路径避免着色理论的空白，特别关注极值情况的结构特征。

核心贡献

路径图的精确公式：给出了路径 $P_n$ 上 $c_k(P_n)$ 和 $cp_k(P_n)$ 的精确公式，并确定了最优着色唯一性的充要条件
树的 $P_4$ 情况完整解决：
- 证明了 $n$ 阶树 $T$ 的 $c_4(T)$ 和 $cp_4(T)$ 最小值为 $(n+2)/2$
- 完全刻画了使 $c_4(T)$ 达到最小值的树（冠图）
- 部分刻画了使 $cp_4(T)$ 达到最小值的树结构
树的 $P_5$ 情况的极值结果：
- 证明了 $c_5(T)$ 和 $cp_5(T)$ 的最小值为 $(n+3)/2$
- 完全刻画了达到最小值的唯一极值图（章鱼图）
重要的结构性引理：建立了图附加操作对参数值影响的一般性结果

方法详解

任务定义

输入：树 $T$ 和正整数 $k$
输出： $c_k(T)$ （任意着色下的最大颜色数）和 $cp_k(T)$ （正常着色下的最大颜色数）
约束：着色不能产生 $k$ 个顶点的彩虹路径 $P_k$

核心方法架构

1. 基础引理（Lemma 1）

对于图附加操作的影响：

若 $G_1$ 由 $G$ 附加 $P_{k-1}$ 到顶点 $w$ 得到，则 $c_k(G_1) = c_k(G) + k - 2$
若 $G_2$ 由 $G$ 在端点 $w$ 附加 $P_{k-2}$ 得到，则 $cp_k(G_2) = cp_k(G) + k - 3$

2. 路径的递推公式

定理1：对于路径 $P_n$ 和 $k \geq 2$ ： $c_k(P_n) = \lfloor\frac{(k-2)n}{k-1}\rfloor + 1$

定理2：对于 $k \geq 3$ ： $cp_k(P_n) = \lfloor\frac{(k-3)n+1}{k-2}\rfloor + 1$

3. 阻断集理论（定理3）

对于树 $T$ ，有等式关系： $c_H(T) = n - \theta_H(T)$ 其中 $\theta_H(T)$ 是 $H$ -阻断数（破坏所有 $H$ 副本所需的最少边数）。

技术创新点

结构分解方法：通过分析图的结构特征（如直径、度数分布）来确定极值图
归纳证明技术：
- 对路径长度的归纳
- 对树的直径的归纳
- 对核心图顶点数的归纳
"无聊顶点"概念：引入顶点分类方法，简化正常着色的分析
构造性证明：不仅证明界的紧性，还给出了具体的极值着色方案

实验设置

理论验证方法

本文采用纯理论方法，通过以下方式验证结果：

具体例子验证：
- $P_{11}$ 不含彩虹 $P_5$ 的最优着色：12344567789（9种颜色）
- $P_{11}$ 不含彩虹 $P_5$ 的最优正常着色：12343565787（8种颜色）
边界情况检验：验证小规模图的情况与公式一致
构造性证明：通过显式构造达到界的着色方案验证结果的正确性

实验结果

主要结果

路径图的精确值

$c_k(P_n)$ 公式： $\lfloor\frac{(k-2)n}{k-1}\rfloor + 1$
$cp_k(P_n)$ 公式： $\lfloor\frac{(k-3)n+1}{k-2}\rfloor + 1$
唯一性条件：
- $c_k(P_n)$ 的最优着色唯一当且仅当 $n$ 是 $k-1$ 的倍数
- $cp_k(P_n)$ 的最优着色唯一当且仅当 $n$ 比 $k-2$ 的倍数多1

树的 $P_4$ 情况

下界： $c_4(T) \geq cp_4(T) \geq \lceil n/2 \rceil + 1$ （定理4）
最小值： $c_4(T)$ 和 $cp_4(T)$ 的最小值为 $(n+2)/2$
极值图：
- 使 $c_4(T) = (n+2)/2$ 的树恰好是冠图（定理5,6）
- 冠图的 $c_4$ 值： $c_4(H) = n/2 + 1$ ，其中 $H$ 是 $n$ 阶冠图