共线图子类的和谐着色问题研究

### 共线图子类的和谐着色问题研究 #### 1. 和谐着色问题定义 和谐着色问题的一种等价表述为：给定图 $G$ 和正整数 $K \leq |V(G)|$，询问是否存在正整数 $k \leq K$ 以及使用 $k$ 种颜色的恰当着色，使得每对颜色最多在一条边上同时出现。 #### 2. 共线图上的和谐着色问题 共线图是余弦图的子类和阈值图的超类。和谐着色问题在余弦图上是 NP 完全的，因为它在分裂图上是 NP 完全的，而在阈值图上有多项式解。所以研究该问题在共线图上的复杂度很有意义。 - **证明思路**：先证明该问题在同时为分裂图和无向路径图的图类上仍是 NP 完全的，再证明每个分裂无向路径图都是共线图，从而得出该问题在共线图上是 NP 完全的。 - **无向路径图的特征**：图 $G$ 是无向路径图当且仅当存在一棵树 $T$，其顶点集为 $G$ 的所有最大团集合 $C$，使得对于 $G$ 中的每个顶点 $v$，由顶点集 $C(v)$（包含 $v$ 的所有最大团集合）诱导的 $T$ 的子图 $T[C(v)]$ 是 $T$ 中的一条路径，这样的树称为 $G$ 的特征树。 #### 3. 分裂无向路径图上的和谐着色问题 通过从一般图的色数问题（已知是 NP 完全问题）进行归约，证明和谐着色问题在分裂无向路径图上是 NP 完全的。 - **构造分裂图 $\tilde{G}$**：设任意图 $G$ 有 $n$ 个顶点 $v_1, v_2, \cdots, v_n$ 和 $m$ 条边 $e_1, e_2, \cdots, e_m$。构造分裂图 $\tilde{G}$，其顶点集 $V(\tilde{G}) = K + I$，其中独立集 $I$ 由 $n$ 个顶点 $\tilde{v}_1, \tilde{v}_2, \cdots, \tilde{v}_n$ 组成，对应图 $G$ 的顶点；团 $K$ 由 $m$ 个顶点 $\tilde{u}_1, \tilde{u}_2, \cdots, \tilde{u}_m$ 组成，对应图 $G$ 的边。顶点 $\tilde{u}_t \in K$（$1 \leq t \leq m$）与两个顶点 $\tilde{v}_i, \tilde{v}_j \in I$（$1 \leq i, j \leq n$）相连当且仅当图 $G$ 中对应的顶点 $v_i$ 和 $v_j$ 相邻。 - **证明 $\tilde{G}$ 是无向路径图**：设 $\tilde{G}$ 的所有最大团集合为 $C$，$K$ 是 $\tilde{G}$ 的一个最大团，所以 $|C| = |I| + 1$。每个顶点 $\tilde{v}_i \in I$ 恰好属于一个最大团，即 $|C(\tilde{v}_i)| = 1$；每个顶点 $\tilde{u}_i \in K$ 恰好属于三个最大团，其中一个是最大团 $K$，即 $|C(\tilde{u}_i)| = |N[\tilde{u}_i]| - |K| + 1 = 3$。考虑顶点集为 $C$ 的树 $T$，使得最大团 $K$ 与每个 $\tilde{v}_i \in I$ 对应的最大团 $C(\tilde{v}_i)$ 都有一条边相连，即 $T$ 是一个星型图。可以证明 $T$ 是 $\tilde{G}$ 的特征树，所以 $\tilde{G}$ 是分裂无向路径图。 - **等价关系**：图 $G$ 的色数为 $\chi(G)$ 当且仅当分裂无向路径图 $\tilde{G}$ 的和谐色数 $h(\tilde{G}) = \chi(G) + m$。 - **正向证明**：在图 $G$ 的最小着色中，将顶点 $v_i$ 分配的颜色 $c_i$ 分配给集合 $I$ 中的顶点 $\tilde{v}_i$，并将集合 $\{\chi(G) + 1, \cdots, \chi(G) + m\}$ 中的不同颜色分配给团 $K$ 中的每个顶点。由于 $G$ 中相邻顶点颜色不同，所以 $\tilde{G}$ 中每个 $\tilde{u}_i \in K$ 属于独立集的邻居颜色不同。每个 $\tilde{v}_i \in I$ 能看到 $G$ 中顶点 $v_i$ 的邻域 $N_G(v_i)$ 个团 $K$ 中的顶点，因此每对颜色最多在一条边上同时出现。分配给集合 $I$ 的颜色数等于 $\chi(G)$，分配给团的颜色数等于 $m$，这就得到了使用 $\chi(G) + m$ 种颜色的 $