根据重构图确定原图

《European Journal of Combinatorics》:Determining a graph from its reconfiguration graph

【字体: 大 中 小 】 时间:2026年09月20日 来源:European Journal of Combinatorics 1.1

编辑推荐:

   **摘要** 给定一个图 $G$ 和一个自然数 $k$,$k$-重着色图 $\mathcal{C}_k(G)$ 是一个图,其顶点为 $G$ 的所有 $k$-着色,其边连接恰在一个顶点处不同的着色对。最近,Hogan 等人证明,当 $k$ 足够大时(即 $G$ 的顶点数的二次量

  

**摘要** 给定一个图 $G$ 和一个自然数 $k$,$k$-重着色图 $\mathcal{C}_k(G)$ 是一个图,其顶点为 $G$ 的所有 $k$-着色,其边连接恰在一个顶点处不同的着色对。最近,Hogan 等人证明,当 $k$ 足够大时(即 $G$ 的顶点数的二次量级),可以从 $\mathcal{C}_k(G)$ 确定 $G$。我们改进了这一界,证明 $k = \chi(G) + 1$ 种颜色已经足够,并给出了若干图族的例子,说明 $k = \chi(G)$ 种颜色并不足够。

随后,我们将此结果推广到 $k$-Kempe 重着色图。该图的顶点同样为图 $G$ 的所有 $k$-着色,其边连接通过对由选定两种颜色所诱导的子图中某个连通分量执行颜色交换而得到的着色对。我们证明,在该情形下 $k = \chi(G) + 2$ 种颜色足以确定 $G$。

最后,我们研究了独立集重构的情形,证明仅在少数平凡情况下才能保证从独立集重构图确定图 $G$。

本文的扩展摘要已在 EuroComb 2025 [3] 上发表。

**1. 引言与主要结果**

**1.1. 单顶点重着色** 设 $G$ 为一个图,$k$ 为正整数。$G$ 的(正常)$k$-着色是将 $[k] \coloneqq \{1, 2, \ldots, k\}$ 中的颜色分配给 $G$ 的顶点的一种方式,使得没有相邻顶点被赋予相同的颜色。$G$ 的色数记为 $\chi(G)$,即 $G$ 存在 $k$-着色的最小 $k$ 值。

$k$-重着色图 $\mathcal{C}_k(G)$ 是一个图,其顶点为 $G$ 的所有 $k$-着色,其边连接恰在一个顶点处不同的 $k$-着色对。在本文中,我们不区分 $\mathcal{C}_k(G)$ 的顶点与其所代表的 $G$ 的着色。

重着色图一直是越来越多的研究的对象。最早被研究的一个方面是将其作为(近乎)均匀随机生成 $k$-着色的工具。其做法是从一个初始着色出发,反复均匀随机地选择一个顶点,并尝试用 $[k]$ 中均匀随机选取的颜色重新着色该顶点。此过程对应于在 $\mathcal{C}_k(G)$ 中执行随机游走。为了使该过程在多项式步数内产生(近乎)均匀分布,$\mathcal{C}_k(G)$ 必须连通且具有多项式直径(这是必要条件但非充分条件)。因此,这两个参数如何随可用颜色数 $k$ 的变化而演变,已成为相当多研究的起点。

由于重构图的连通性对许多应用至关重要,关于不同重构图连通性问题的计算复杂性方面也已做了大量研究。许多此类判定问题已知在算法上是困难的(通常为 PSPACE-完全)。感兴趣的读者可参阅综述 [4]、[7]。

其他重构图也被研究过,有些已有很长历史。例如,纽结图的 Reidemeister 变换可视为不同纽结表示之间的边。此外,解魔方等价于在某个重构图中找到两个构型之间的路径。

根据定义,给定 $G$ 和 $k$ 即可完全确定 $\mathcal{C}_k(G)$。2024 年初,Asgarli 等人 [2] 提出了反向问题是否成立。更具体地,他们猜想每个图 $G$ 都由重着色图集 $\mathcal{C}_k(G)$,$k \in \mathbb{Z}^+$ 唯一确定。此外,他们猜想每个图 $G$ 实际上都可由这些重着色图的某个有限子集唯一确定。不久之后,Hogan 等人 [5] 在强意义下回答了这些猜想,证明单个重着色图 $\mathcal{C}_k(G)$ 就足以确定 $G$,前提是 $k$ 足够大。

**定理 1.1** Hogan 等人 [5] 设 $G$ 为 $n$ 个顶点的图。若 $k > 5n^2$,则可从重着色图 $\mathcal{C}_k(G)$ 确定 $G$,假设我们已知 $k$。

我们的第一项贡献是改进定理 1.1:首先证明小得多的 $k$ 已足够,其次移除预先知道 $k$ 的值这一假设。

**定理 1.2** 设 $G$ 为一个图。若 $k > \chi(G)$,则可从 $\mathcal{C}_k(G)$ 确定 $G$,即使不知道 $k$ 的确切值。

与 [5] 中的结果类似,定理 1.2 的证明提供了一个恢复算法,该算法关于 $\mathcal{C}_k(G)$ 的大小(一般关于 $G$ 的大小呈指数关系)在多项式时间内运行。然而,我们可以证明通过使用更多颜色,可将恢复算法改进为关于 $|V(G)|$ 在多项式时间内运行。

**定理 1.3** 设 $G$ 为 $n$ 个顶点、最大度 $\Delta \geq 1$ 的图。若 $k > \min\{n, 2\Delta\}$,则可从 $\mathcal{C}_k(G)$ 确定 $G$,即使不知道 $k$ 的确切值,只需考虑 $\mathcal{C}_k(G)$ 中至多 $(kn)^2$ 个不同着色。

此外,若 $\Delta = 0$,即 $G$ 没有边,则我们的证明给出若 $k > 1$ 可轻松从 $\mathcal{C}_k(G)$ 确定 $G$。定理 1.2 和定理 1.3 的证明大部分利用了 [5] 中定理 1.1 证明已存在的观察。然而,[5] 中的作者使用了计数论证,而我们利用了更多的结构观察。

定理 1.2 中颜色数的界是紧的:当 $k = \chi(G)$ 时,图 $G$ 未必由其 $k$-重着色图 $\mathcal{C}_k(G)$ 唯一确定。例如,任何连通二部图的 2-着色图都是具有两个顶点且无边的一条图。对于任意 $\chi \geq 2$,任何 $(\chi-1)$-树(由以下步骤构造的任意图:从 $\chi$ 个顶点的完全图开始,添加一个顶点 $v$ 使得 $v$ 的邻居构成 $\chi-1$ 个顶点的团,并重复此过程有限次)的 $\chi$-重着色图都是具有 $\chi!$ 个顶点且无边的一条图。

这些例子利用了图 $G$ 中某些顶点被冻结的事实,即它们在任何 $\chi(G)$-着色下都无法被重新着色。如果图 $G$ 包含任何冻结顶点,则其重着色图不唯一。可以验证:在 $G$ 中添加一个新顶点,使其具有与某个冻结顶点 $v$ 相同的邻居集。新图将与 $G$ 具有相同的 $\chi(G)$-重着色图。

然而,我们将证明冻结顶点的存在不是图 $G$ 具有非唯一 $\chi(G)$-重着色图的必要条件。

**定理 1.4** 对每个 $\chi \geq 6$,存在一个任意大的非同构图族 $\mathcal{F}$,所有图均具有色数 $\chi$ 且没有冻结顶点,使得对任意 $G, G' \in \mathcal{F}$ 均有 $\mathcal{C}_\chi(G) \cong \mathcal{C}_\chi(G')$。

注意所有这些结果可轻松推广到边着色的情形,因为对图 $G$ 的边着色等价于对 $G$ 的线图进行顶点着色。特别是,当 $k$ 大于 $G$ 的边色数时,可从 $G$ 的 $k$-边重着色图确定 $G$ 的线图。利用 Whitney 的经典定理 [8],这使得 $G$ 除与三角形、3-边星或单个顶点同构的连通分量外均可被确定。

注:在我们将本文发布到 arXiv 后不久,Asgarli 等人 [1] 上传了一篇包含与本小节结果相似的论文。特别地,他们证明了定理 1.2 的一个非平凡推广:若 $G$ 是一个图且 $k > \chi(G)$,则对任意图 $G'$ 均有 $\mathcal{C}_{\chi(G')}(G') \not\cong \mathcal{C}_k(G)$。

**1.2. Kempe 重着色** 在前一部分中,我们考虑了每次仅改变一个顶点颜色的重构图。在涉及重着色的问题中,还有一种自然要考虑的运算:执行 Kempe 交换。给定图的一个 $k$-着色,Kempe 交换是指在由给定两种颜色所诱导的最大连通子图中交换这两种颜色。注意单顶点重着色是 Kempe 交换的一个特例,称为平凡 Kempe 交换。

Kempe 交换运算引出 $k$-Kempe-重着色图 $\mathcal{K}_k(G)$ 的定义,其顶点为 $G$ 的所有 $k$-着色,其边连接通过单次 Kempe 交换彼此不同的 $k$-着色对。注意 $\mathcal{C}_k(G)$ 和 $\mathcal{K}_k(G)$ 具有相同的顶点集,而平凡 Kempe 交换表明 $E(\mathcal{C}_k(G)) \subseteq E(\mathcal{K}_k(G))$。如前所述,我们不区分 $\mathcal{K}_k(G)$ 的顶点与其所代表的 $G$ 的 $k$-着色。

我们将之前的结果推广到 Kempe 重着色的情形。我们证明当 $k$ 足够大时,可以识别 $\mathcal{K}_k(G)$ 中哪些边对应于平凡 Kempe 交换。换句话说,我们可以识别 $\mathcal{K}_k(G)$ 中哪些边诱导了 $\mathcal{C}_k(G)$ 的副本,从而应用单顶点重着色情形的相应机制。

**定理 1.5** 设 $G$ 为一个图。若 $k > \chi(G) + 1$,则可从 $\mathcal{K}_k(G)$ 确定 $G$,即使不知道 $k$ 的确切值。

用于定理 1.4 的相同例子表明,当 $k = \chi(G)$ 时 Kempe-重着色图也不是唯一的。这留下了 $k = \chi(G) + 1$ 的情形未解决。

**问题 1.6** 每个图 $G$ 能否从 $\mathcal{K}_{\chi(G)+1}(G)$ 确定?

与单顶点重着色情形类似,定理 1.5 的证明提供了一个关于 $\mathcal{K}_k(G)$ 大小在多项式时间内运行的恢复算法。当使用的颜色数足够大时,该算法可改进为关于 $|V(G)|$ 在多项式时间内运行。

**定理 1.7** 设 $G$ 为 $n$ 个顶点、最大度 $\Delta \geq 1$ 的图。若 $k > \min\{n, 2\Delta\} + 1$,则可从 $\mathcal{K}_k(G)$ 确定 $G$,即使不知道 $k$ 的确切值,只需考虑 $\mathcal{K}_k(G)$ 中至多 $(kn)^2$ 个不同着色。

**1.3. 独立集重构** 在最后一部分中,我们研究独立集重构的领域。图中的独立集是指两两不相邻的顶点集合。我们将每个独立集解释为放置在其顶点上的标记(token)集合,并允许标记根据以下三种规则之一移动(前提是独立集性质不被破坏):

- **标记跳跃(Token Jumping,简称 TJ)**:一个标记可以移动到任何其他顶点。
- **标记滑动(Token Sliding,简称 TS)**:标记只能移动到相邻顶点。
- **标记添加和移除(Token Addition and Removal,简称 TAR)**:可以添加或移除单个标记。

给定图 $G$,我们用 $\mathcal{I}_k^J(G)$ 表示在 TJ 规则下所有大小为 $k$ 的独立集的重构图。换句话说,$\mathcal{I}_k^J(G)$ 的每个顶点对应于 $G$ 中一个大小为 $k$ 的独立集,每条边对应一次有效的标记跳跃。类似地定义 $\mathcal{I}_k^S(G)$。

注意 TJ 和 TS 保持标记数量不变,但 TAR 并非如此。因此 TAR-重构图的定义略有不同:$\mathcal{I}_k^{AR}(G)$ 对 $G$ 中每个大小至少为 $k$ 的独立集有一个顶点,每条边对应一次标记添加或移除操作。

结果表明,独立集重构的情形与我们之前为重着色所看到的情况大不相同。除少数平凡情形外,不能保证从上述定义的标记重构图中确定 $G$。更精确地,我们证明如下。

**定理 1.8** 设 $G$ 为一个图。若 $R = S$ 且 $k = 1$,或 $R = AR$ 且 $k \in \{0, 1\}$,则可从 $\mathcal{I}_k^R(G)$ 确定 $G$。在所有其他情况下,存在非同构图 $G$,其独立集重构图同构。

**本文组织结构。** 接下来的每一节分别致力于上述三个主题之一。我们给出所述结果的证明并讨论表明这些结果具有紧性的例子。

**2. 单顶点重着色——证明与例子** 我们从定理 1.2 和定理 1.3 的证明开始。设 $G$ 为 $n$ 个顶点的图,$k > \chi(G)$。我们确定 $G$ 的方法如下:首先,对 $\mathcal{C}_k(G)$ 的每个着色 $c \in V(\mathcal{C}_k(G))$,利用 $\mathcal{C}_k(G)$ 在 $c$ 附近的局部结构构造 $G$ 的候选图 $G_c$。更精确地,对 $c$ 的邻域 $N_{\mathcal{C}_k(G)}(c)$ 中的每个极大团 $C$,$G_c$ 都有一个顶点 $v_C$;若存在 $u \in C$ 和 $u' \in C'$ 使得它们在 $\mathcal{C}_k(G)$ 中的唯一公共邻居为 $c$,则在 $v_C$ 和 $v_{C'}$ 之间连一条边。然后我们证明每个候选图都是 $G$ 的子图,且至少有一个候选图实际上是 $G$ 本身。

这使得我们可以通过选择具有最大顶点数和边数的候选图来识别 ??。此外,如果我们进一步假设 ??>min{??,2??},我们将证明所有这些候选图都与 ?? 同构,这使我们能够通过选择任何着色 ??∈??(????(??)) 并仅查看 ????(??) 中距离 ?? 为 1 和 2 的顶点来确定 ??。首先我们研究 ????(??) 中邻域的结构。我们以 [5] 中已经陈述的一个观察开始:????(??) 中每个大小至少为 2 的团 ?? 都是由 ?? 的着色形成的,这些着色仅在 ?? 的一个顶点上不同。我们将此顶点记为 ????。利用此属性,我们观察到 ????(??) 中每个着色 ?? 的邻域诱导了 ?? 个(可能为空)团的并集,每个团对应 ?? 的一个顶点。对于每个 ??∈??(????(??)) 和 ??∈??(??),我们用 ????,?? 表示 ????(??) 中包含所有仅在与 ?? 在 ?? 处不同的着色的团(如果不存在这样的着色,则 ????,?? 为空)。对于每个着色 ??∈??(????(??)),候选图 ???? 中的顶点数将是其邻域中的连通分量数,这至多为 ??。为了确定 ?? 的边,我们将考虑 ????(??) 中距离为 2 的邻域。
引理 2.1 设 ?? 为 ?? 的一个 ??-着色。如果 ???????(??),则每个 ????∈??(????,??) 和 ????∈??(????,??) 都有一个不同于 ?? 的公共邻居 (?)。
证明 给定 ????∈??(????,??) 和 ????∈??(????,??),定义 ?? 的一个 ??-着色 ??′ 如下:??′(??)=????(??),??′(??)=????(??),且对于每个 ???{??,??},??′(??)=??(??)。注意 ??′≠??,且 ??′ 与 ????(分别与 ????)仅在 ??(与仅在 ??)处不同。此外,由于 ?? 和 ?? 不相邻,?? 及其所有邻居在 ??′ 和 ???? 下被分配相同的颜色,?? 及其所有邻居在 ??′ 和 ???? 下被分配相同的颜色。由于 ???? 和 ???? 是 ?? 的正常着色,我们得出结论 ??′ 是 ?? 的一个正常着色。□
引理 2.1 中的条件 (?) 给出了一个确定 ?? 边的部分准则。我们现在考虑 ????(??) 中的每个着色 ?? 并构建相应的候选图 ???? 如下。对于每个 ??∈??(????(??)),设 ???? 为具有 ??????(??)(??) 的每个极大团 ?? 对应一个顶点 ???? 的图,当且仅当团 ?? 和 ??′ 不满足 (?) 时(即当且仅当存在 ??∈?? 和 ??′∈??′ 没有不同于 ?? 的公共邻居时),两个顶点 ???? 和 ????′ 之间有一条边。由引理 2.1,?? 的每个非边也是 ???? 的非边,这给出了以下推论。
推论 2.2 对于 ?? 的每个 ??-着色 ??,???? 是 ?? 的子图。
剩下需要证明的是,对于至少一个 ?? 的选择,???? 与 ?? 同构。这一论证来自以下观察。
引理 2.3 设 ????∈??(??) 且设 ?? 为 ?? 的一个 ??-着色,使得存在一个颜色 ??∈[??] 不出现在 {??,??}∪??(??)∪??(??) 中。那么 (?) 不成立。
证明 定义 ????(分别为 ????)为通过将 ?? 中的 ??(分别为 ??)重新着色为颜色 ?? 得到的着色。注意 ???? 和 ???? 仅在 ?? 和 ?? 上不同,因此任何不同于 ?? 且与 ???? 和 ???? 都相邻的着色 ??′ 必须给 ?? 和 ?? 都分配颜色 ??。但由于 ?? 和 ?? 相邻,不存在这样的着色。□
如果我们假设 ??>??(??),那么对于任何仅使用 ??(??) 种颜色的 ?? 的 ??-着色 ??′,存在一个颜色 ??∈[??] 完全未被 ??′ 使用。结合推论 2.2 和引理 2.3,我们得出对于任何这样的 ??′,????′ 与 ?? 同构。此外,由于推论 2.2 告诉我们对于每个 ??∈??(????(??)),???? 是 ?? 的子图,我们可以通过考虑所有候选图的集合 {????∣??∈??(????(??))} 并选择其中顶点和边数最多的任意一个来识别这样的 ??′。这完成了定理 1.2 的证明。此外,如果我们进一步假设 ??>min{??,2??},则引理 2.3 中的条件对于 ?? 的每个 ??-着色 ?? 都成立。因此,在这种情况下,????(??) 中的每个 ?? 的 ???? 都与 ?? 同构。给定 ????(??) 中的一个着色 ??,为了确定 ????,我们只需要考虑 ????(??) 中距离 ?? 为 1 和 2 的着色。观察到任何着色在 ????(??) 中至多有 (???1)?? 个邻居,因此在这种情况下,我们可以考虑至多 (????)^2 个 ????(??) 中的着色来确定 ??,从而完成定理 1.3 的证明。
2.1. 情形 ??=??(??)
当 ??=??(??) 时,情况变得非常不同。首先,在某些情况下(例如如果 ?? 是一个团),图 ?? 可能包含一些顶点,其闭邻域在 ?? 的每个正常 ??-着色下都包含所有可用的 ?? 种颜色,因此永远无法重新着色。我们将这些顶点称为冻结的。如果一个顶点至少在 ?? 的一个 ??(??)-着色中可以改变颜色,我们称之为可重着色的。在引言中,我们展示了如果图包含冻结顶点,则其 ??(??)-重着色图不是唯一的。在下一个定理中,我们将展示这不是必要条件。
定理 1.4 对于每个 ??≥6,存在任意大的非同构图族 ?,它们都有色数 ?? 且没有冻结顶点,使得对于所有 ??,??′∈?,有 ????(??)?????(??′)。
我们的构造依赖于 Mycielski [6] 的经典构造。设 ?? 为具有顶点 ??1,…,???? 的 ??-顶点图。那么 ?? 的迈希尔斯基安 ??(??) 是通过添加顶点 ??1,…,???? 和 ??,添加 ?? 与每个 ???? 之间的边,以及对于每个 ????????∈??(??) 添加边 ???????? 和 ???????? 来构造的。我们使用符号 ??^2(??)=??(??(??)),以此类推。这个构造的基本性质是对于每个 ?? 和图 ??,??(??^??(??))=??(??)+?? [6]。
我们现在给出构造,以提供定理 1.4 中承诺的例子。
构造 2.4 设 ??≥6 且 ??∈[3,???3]。设 ??0 和 ??3 为任意两个图,使得 ??(??0)注意到由于 ??0 和 ??3 可以选为任意大,? 可以任意大。
构造 2.4 中定义的图 ??0 如图 1 所示。灰色区域表示两个图之间的所有边在 ??0 中均存在。
构造 2.4 的主要思想如下。图 ??0 的色数为 ?? 且没有冻结顶点。另一方面,在 ??0 的每个 ??-着色下,分配给 ??0 中顶点的颜色与分配给 ??3 中顶点的颜色是不相交的。后者性质意味着添加 ??0 和 ??3 之间的边不会影响 ??0 的 ??-重着色图。
下载:下载高分辨率图像 (92KB) 下载:下载全尺寸图像
图 1. 构造 2.4 中色数为 ?? 的图 ??0。灰色区域表示完全连接。
为了证明集合 ? 满足定理 1.4 的要求,我们需要一个进一步的观察。
引理 2.5 设 ?? 为没有冻结顶点的图。那么 ?? 的迈希尔斯基安 ??(??) 没有冻结顶点。
证明 正如图的迈希尔斯基安定义中那样,我们将 ?? 的顶点记为 ??1,…,????,将 ??(??) 的顶点记为 ??1,…,????,??1,…,????,??。设 ??=??(??) 且固定 ??∈[??]。由于 ?? 没有冻结顶点,存在 ?? 的一个 ??-着色 ??,使得 ???? 是可重着色的。设 ???? 为 ??(??) 的着色,其中对于每个 ??∈[??],????(????)=????(????)=??(????),且 ????(??)=??+1。由于 ??(??(??))=??(??)+1,这个 ??(??) 的着色使用了最少数量的颜色。注意 ???? 和 ???? 在 ???? 中是可重着色的。由于 ??∈[??] 是任意的,??1,…,????,??1,…,???? 都不是冻结的。
接下来设 ?? 为 ?? 的任何着色,设 ???? 为由 ????(????)=??(????) (每个 ??∈[??]), ????(????)=??+1 (每个 ??∈[??]), 且 ????(??)=1 给出的 ??(??) 的着色。那么 ?? 在 ???? 中是可重着色的,因此 ?? 不是冻结的。□
定理 1.4 的证明 设 ??≥6, ??, ??0,??1,??2,??3, ??0 和 ? 如构造 2.4 所示。如已观察到的,? 可以任意大,因为 ??0 和 ??3 可以任意大。
由于 ??(??5)=3,对于 ??1,??2 我们有 ??(??1)=??(??^(???3)(??5))=?? 且 ??(??2)=??(??^(??????3)(??5))=?????。因此,由构造可知,? 中的每个 ?? 的色数为 ??。
接下来我们证明对于每个 ??∈?,?? 的所有顶点都是可重着色的。观察到长度为 5 的圈 ??5 没有冻结顶点。因此,由引理 2.5,??1=??^(???3)(??5) 和 ??2=??^(??????3)(??5) 没有冻结顶点。
固定 ?1∈??1 并设 ??1:??(??1)→[??] 为使得 ?1 可重着色为某个 ??∈[??] 的 ??-着色。固定 ?2∈??2 并设 ??2:??(??2)→[??+1,??] 为使得 ?2 可重着色为某个 ??∈[??+1,??] 的 (?????)-着色。考虑 ??0 的任何 (??????1)-着色 ??0:??(??0)→[??+1,???1] 和 ??3 的任何 (???1)-着色 ??3:??(??3)→[???1]。设 ?? 为 ? 中的一个图(因此 ??(??)=??(??0)∪?∪??(??3)),并通过复制 ?? 的不同部分的 ??0,…,??3 来形成 ?? 的 ??-着色 ??。
注意无论 ?? 中 ??0 和 ??3 之间有什么边,??0 中的每个顶点都可重着色为 ??,且 ??3 中的每个顶点都可重着色为 ??。此外,?1 和 ?2 分别可重着色为 ?? 和 ??。由于 ?1 和 ?2 分别是 ??1 和 ??2 中的任意元素,我们已证明 ? 中任意 ?? 的所有顶点都是可重着色的。
剩下需要证明的是 ? 中的每个图具有相同的 ??-重着色图。我们使用以下断言。
断言 设 ?? 为色数为 ?? 的图,并假设 ???????(??) 满足对于 ?? 的所有 ??-着色 ?? 都有 ??(??)≠??(??)。设 ??′ 为由添加边 ???? 从 ?? 形成的图。那么 ????(??)?????(??′)。
断言的证明 显然 ??(??′)=??(??) 且 ????(??′) 是 ????(??) 的子图。剩下需要证明的是 ????(??) 也是 ????(??′) 的子图。设 ??∈??(????(??))。那么 ??(??)≠??(??),所以 ?? 是 ??′ 的正常着色,因此 ??∈??(????(??′)),这给出了 ??(????(??))???(????(??′))。现在设 ??1??2∈??(????(??))。那么 ??1 和 ??2 是 ?? 的 ??-着色,它们在 ?? 的某个顶点 ?? 处不同且其他地方都相同,因此(由于 ??(????(??))???(????(??′))),??1 和 ??2 是 ??′ 的 ??-着色,它们在 ??′ 的某个顶点 ?? 处不同且其他地方都相同。这意味着 ??1??2∈??(????(??′)),因此 ??(????(??))???(????(??′)) 如要求所示。□
设 ?? 为 ??0 的一个 ??-着色。对于 ??∈{1,2},设 ???? 为 ?? 分配给 ???? 中顶点的颜色集合,即 ????={??∈[??]∣???∈??(????),??(??)=??}。观察到 ??1∩??2=?,因为 ??1 的每个顶点都与 ??2 的每个顶点相邻。我们还有 |??2|≥?????,因为 ??1 和 ??2 的色数分别为 ?? 和 ?????。这给出了 ??1∪??2=[??], |??1|=??,以及 |??2|=?????。设 ??∈??0 且 ??∈??3。那么 ??(??)???1,因为 ?? 与 ??1 中的每个顶点相邻;因此 ??(??)∈??2。类似地,我们有 ??(??)∈??1。这给出了 ??(??)≠??(??)。
因此,在 ??0 的每个 ??-着色下,??0 的每个顶点被分配的颜色与 ??3 的每个顶点被分配的颜色都不同。根据上面的断言,这意味着由添加 ??0 和 ??3 顶点之间的边从 ??0 形成的任何图 ?? 都将具有与 ??0 相同的 ??-重着色图,从而完成了定理的证明。□
3. 肯普重着色 – 证明和例子
对于 ?? 的一个 ??-着色 ?? 和 ??∈??(??),我们用 ????,?? 表示由 ?? 通过对 ?? 进行平凡肯普交换得到的 ????(??) 中的着色集合。平凡肯普交换对应于第 2 节中讨论的单顶点重着色操作,因此对于每个 ??∈??(??),????,?? 仍然是一个团。我们用 ???? 表示 ?? 在 ????(??) 中的其他邻居集合,即那些对应于通过非平凡肯普交换从 ?? 得到的 ?? 的着色的顶点。
与单顶点重着色的情况类似,我们首先研究 ????(??) 中每个着色 ?? 的邻域诱导的图。

我们证明,与之前一样,每个这样的图中每个连通分量都是团,并且任何尚未位于????(??)中??的邻域中的这样的团都是一个孤立顶点。

**引理 3.1** 对于??的任意??-染色??和不同的??,??∈??(??),在????(??)中????,??和????,??之间不存在边。

**证明** 设????∈????,??且????∈????,??。假设????????∈??(????(??))。那么我们可以通过一次Kempe交换从????移动到????。由于????和????仅在??和??上不同,在??的所有其他顶点上一致,因此该Kempe交换仅影响??和??。这意味着{??,??}必须诱导??的一个连通子图,因此????∈??(??)。另一方面,我们有????(??)=??(??)和????(??)=??(??)。从????到????的Kempe交换之后,??的颜色变为????(??),即我们有????(??)=????(??)。但这意味着??(??)=??(??),因此???????(??),矛盾。□

**引理 3.2** 对于??的任意??-染色??和??∈??(??),????是????(??)的一个独立集,且在????,??中没有邻居。

**证明** 设??1∈????且??2∈????∪????,??,其中??1≠??2。设??1,分别记为??2,为在??与??1之间,分别是在??与??2之间执行的Kempe交换所涉及的颜色的集合(当??2∈????,??时,这意味着??2={??(??),??2(??)})。那么|??1|=|??2|=2。如果|??1∪??2|≥3,则在??1和??2不同的顶点集合上至少出现三种颜色,因此我们不能通过单次Kempe交换从??1移动到??2。所以??1=??2。假设??2∈????。那么由于??1≠??2,??中由??1和??2不同的顶点集合所诱导的子图恰好由两个连通分量组成。因此在这种情况下我们不能通过Kempe交换从??1移动到??2。所以??2∈????,??。设??:=??2(??),且令??1=??2={??,??}。设??为在从??到??1的Kempe交换中改变颜色的??的顶点集合。由于|??|≥2,??中的每个??要么满足??(??)=??,要么有邻居??∈??使得??(??)=??。因此我们必然有?????,因为从??到??2的移动将??的颜色变为??。由于??1=??2,这意味着??和??之间没有边。因此,??中由??1和??2不同的顶点集合所诱导的子图恰好由两个连通分量组成,因此在这种情况下我们也无法通过Kempe交换从??1移动到??2。□

**引理 3.3** 设??为??的一个??-染色,设??,??∈??(??)使得|????,??|,|????,??|≥2,且设????∈????,??和????∈????,??。如果???????(??),则|??????,??|≥2且|??????,??|≥2。

**证明** 由于|????,??|≥2,在??中有至少两种颜色可用于重新染色??。然而,??和????仅在??上不同,而我们假设??不与??相邻。因此我们也可以用这两种颜色对????中的??重新染色,故|??????,??|≥2。类似的论证表明|??????,??|≥2。□

**引理 3.4** 设??为??的一个??-染色。如果???????(??),则对于每个????∈????,??和????∈????,??,我们有??????,??∩??????,??≠?。

**证明** ??与????之间以及??与????之间的转换是平凡的Kempe交换,因此根据引理2.1,??????,??∩??????,??非空。□

给定??的一个??-染色??以及??,??∈??(??),??≠??,使得|????,??|,|????,??|≥2,我们说????∈????,??和????∈????,??满足条件(??)是指:????和????有一个除??以外的公共邻居??,且存在染色??1,??2使得{??,????,??1}和{??,????,??2}都在????(??)中诱导三角形。

下面的引理告诉我们,满足条件(??)等价于引理3.3和引理3.4的结论同时成立。

**引理 3.5** 设??为??的一个??-染色,设??,??∈??(??),??≠??,使得|????,??|,|????,??|≥2。那么????∈????,??和????∈????,??满足(??)当且仅当|??????,??|≥2,|??????,??|≥2,且??????,??∩??????,??≠?。

**证明** 如果(??)成立,则由引理3.1和引理3.2,我们必须有??,??1∈??????,??且??,??2∈??????,??。反过来,如果|??????,??|≥2,|??????,??|≥2,且??????,??∩??????,??≠?,则通过选取任意??∈??????,??∩??????,??,??1∈??????,???{??},以及??2∈??????,???{??},(??)成立。□

我们现在可以改编定理1.2的证明来获得定理1.5。与之前类似,我们将利用????(??)的每个顶点??通过观察其在距离2处的邻域来构造??的候选图????,具体方法如下。固定??∈????(??)。对于每个大小至少为2的最大团????,??,在????中创建一个顶点??,使得??(????)???(??)。(注意,根据引理3.2,我们可以识别这样的????,??。)然后在????中的两个顶点??和??之间放置一条边,当且仅当存在一对????∈????,??和????∈????,??使得条件(??)不满足。(注意,这是我们很容易检查的。)由引理3.3、3.4和3.5,如果????∈??(????),则????∈??(??)。换句话说,每个候选图????都是??的子图。

不幸的是,忽略大小为1的团可能会移除一些????,??,其中??在其闭邻域中恰好看到???1种颜色。然而,我们仍然可以证明以下结论。

**引理 3.6** 如果??>??(??)+1,则????(??)中每个使用至多???2种颜色的染色??都满足???????。

**证明** 设??∈??(????(??))是一个使用至多???2种颜色的染色,设??,??∈[??]为??未使用的颜色。注意,??的每个顶点??都可以通过一次平凡的Kempe交换重新染色为颜色??和??。因此对于每个??∈??(??)都有|????,??|≥2,所以??(????)=??(??)。由于我们已知????是??的子图,只剩下证明??的每条边都包含在????中。假设????∈??(??)。设????(分别记为????)为??(分别为??)被重新染色为颜色??的染色。如果存在某个??′∈??????,??∩??????,??,则??′(??)=??=??′(??),矛盾。所以??????,??∩??????,??为空。因此,根据引理3.5,????和????不满足(??)。故????∈??(????)。□

特别地,如果??>??(??)+1,则对任何仅使用??(??)种颜色的??-染色??应用引理3.6,会得到一个与??同构的候选图????。与单顶点重新染色的情况类似,由于所有候选图都是??的子图,我们可以通过选择具有最大顶点数和边数的候选图来识别与??同构的候选图。这就完成了定理1.5的证明。

**定理1.7的证明** 只需要少量的额外工作。

如果??>min{??,2Δ}+1,则在??的任何??-染色下,??的每个顶点都可以用至少两种颜色重新染色。正如引理3.6证明中的论证那样,我们知道对于??的任何??-染色??,????都与??同构。给定这样的??-染色??,从??出发的每次Kempe交换都由选择一个顶点??和一个颜色??≠??(??)来确定:在包含??的具有颜色??(??)和??的最大诱导子图上交换颜色??(??)和??。这意味着从??的任何??-染色出发,最多有????次Kempe交换是可能的。因此??的任何??-染色在????(??)中距离1或2处最多有(????)2个邻居,从而完成了定理1.7的证明。□

第2.1节中关于单顶点重新染色的相同例子表明,一般来说,图??无法从其??(??)-Kempe-重染图来确定。例如,任何(???1)-树的??-Kempe-重染图是??!个顶点上的图,每个顶点对应{1,…,??}的某个排列,其中两个顶点之间存在边当且仅当它们对应的排列通过交换两个元素(颜色)而不同。类似地,定理1.4中的构造同样适用于Kempe-重染的情况,因为正如之前所观察到的,给定图??,在任意??(??)-染色下永远无法被赋予相同颜色的两个顶点之间添加一条边,不会改变其??(??)-Kempe-重染图,即使我们现在允许非平凡的Kempe交换也是如此。

然而,任何图??是否可以由其(??(??)+1)-Kempe-重染图来确定,这一问题仍然是开放的。

## 4. 独立集重构——证明与示例

在本节中,我们研究是否可以从独立集重构图来确定图??,通过证明定理1.8。我们首先考虑??∈{0,1}时的三种情况(TJ、TS和TAR)。

TS和TJ情形对于??∈{0,1}由以下直接观察得到。

**观察4.1** 设??为一个图。则?0J(??)和?0S(??)是单个顶点,?1J(??)是一个团,?1S(??)同构于??。

TAR情形需要更多工作,因此我们分别为??=0和??=1两种情况安排独立的部分。

### 4.1 标记添加与移除,??=0

为了从重构图?0AR(??)确定??,我们将证明所需的所有信息都包含在任何最大度顶点的邻域中。首先注意到?0AR(??)中顶点的度数最多为??=|??(??)|,因为我们每次只能添加或移除一个标记。由于空集恰好有??个邻居,我们得知?0AR(??)的最大度数为??。

我们开始刻画?0AR(??)中具有最大度的顶点。根据上述观察,??的最大度独立集的邻居恰好对应于在??的某个顶点上添加或移除一个标记。因此,我们可以用??(??)来索引?0AR(??)中任何度数为??的顶点??的邻域。这样一个??的邻域是族(????)??∈??(??),其中????表示对称差???{??}(通过在??的顶点??上添加或移除标记从??得到的独立集)。

**引理4.2** 设??是?0AR(??)中一个最大度的顶点,设????和????是??的两个邻居。则???????(??)当且仅当????和????在?0AR(??)中有一个公共邻居??′≠??。

**证明** (?) 假设???????(??),设??′=???{??,??}=?????{??}=?????{??}。集合??′是一个独立集,因为???????(??)。此外,??′≠??,且????和??′仅在顶点??上不同,所以??????′∈??(?0AR(??))。由??和??的对称性,我们也有??????′∈??(?0AR(??))。

(?) 现在假设????∈??(??)。则??和??不能同时属于??的一个独立集,因此??,????,????不能同时包含??和??。由于??或????中包含??,它们都不可能包含??,类似地??和????不包含??。因此??∈????且??∈????。但随后?0AR(??)中????和????的任何邻居??′≠??都必须同时包含??和??,矛盾。□

上述引理给出了一个从重构图?0AR(??)确定??的算法。该算法运行时间为|?0AR(??)|的多项式。然而,当空独立集不被允许时,问题变得更加复杂,我们将在下一部分中看到。

### 4.2 标记添加与移除,??=1

从?1AR(?1AR)确定??依赖于确定?1AR(??)中每个顶点对应的??的独立集的大小。事实上,一旦知道了这个,就可以通过为每个大小为1的独立集关联一个顶点,当这些独立集不共享大小为2的邻居时添加边,从而确定图??。

为此,我们引入图的分层。给定图??,??的一个分层是??(??)的一个划分,分为部分??1,…,???(每个部分????称为一层),使得:

1. 每一层都是??的独立集。
2. 每一层仅在与它直接相邻的上一层和下一层中有邻居。
3. 对于2≤??≤?,第??层中的每个顶点在第???1层中有??个邻居。
4. 对于1≤??≤?,第??层中任意两个顶点在第???1层中最多有一个公共邻居,在第??+1层中最多有一个公共邻居。

注意,并非所有图都存在这样的分层。特别地,如果一个图不是二部图,则根据以上四个条件,不可能对其顶点进行划分。然而,我们将证明,将任何图??的独立集按其大小划分,会产生?1AR(??)的"自然"分层。

为方便起见,在本节余下部分中,我们使用相同的字母表示??的一个独立集及其在?1AR(??)中对应的顶点。

**引理4.3** 对于图??,对于??=1,…,??(??),设????为??中大小为??的独立集的集合。则??1,…,????(??)是?1AR(??)的一个分层。

**证明** 设??为??的一个独立集。由于TAR规则由添加或移除标记组成,??在?1AR(??)中的邻居是大小为|??|+1或|??|?1的独立集,这表明条件1和2都成立。

我们有{I?{v}∣v∈I}?V^{|I|?1}是I的所有大小为|I|?1的邻居的集合,因此条件3成立。最后,设I和J是两个大小相同的独立集。如果它们通过交换至少两个顶点来区分,则它们没有公共邻居。假设它们恰好通过交换一个顶点来区分。那么它们在V^{|I|?1}中恰好有一个公共邻居(I∩J),并且在V^{|I|+1}中至多有一个公共邻居(I∪J),因此条件4成立。□

为了结束图G可以从??AR(G)确定的证明,我们首先证明引理4.4,表明??AR(G)具有唯一的分层,除了一个非常特殊的情形。然后我们在引理4.5和引理4.6中处理这个例外情形。

**引理4.4** 设G是一个图,使得??AR(G)没有连通分量是偶圈。那么引理4.3中定义的??AR(G)的分层是??AR(G)的唯一分层。

**证明** 设V?,…,V_l是??AR(G)的一个分层。我们通过关于p的归纳证明每个V_p只包含大小为p的独立集,除了??AR(G)中形成偶圈的连通分量。

**基础情形p=1。** 我们首先证明V?不包含大小至少为3的独立集。否则,设I=J∪{u,v},u≠v且J≠?,是这样一个大独立集。由条件2,I的所有邻居都在V?中,因此I?=J∪{u}和I?=J∪{v}都在V?中。由条件3,I?在V?中必须有另一个不同于I的邻居,该邻居要么是I??{x}(对某个x∈I?),要么是I??=I?∪{y?}(对某个y??I)。第一种情况是不可能的,因为它意味着I?和I?{x}是I和I??{x}在V?中的公共邻居,这与条件4矛盾。因此,I?在V?中的邻居是I和I??。由相同的论证我们得到I?在V?中有邻居I和I??=I?∪{y?}(对某个y??I)。由于I?和I?在V?中已经有一个公共邻居I,由条件2和4,另一个公共邻居J必须在V?中。接下来注意到I???{u}=J∪{y?}和I???{v}=J∪{y?}由条件2都在V?中。所以J在V?中有邻居I?、I?、J∪{y?}、J∪{y?}。由条件3,J在V?中只能有三个邻居,所以我们必须有y?=y?。现在我们有I=J∪{u,v}、I??=J∪{u,y?}和I??=J∪{v,y?}都是V?中的独立集。这意味着J∪{u,v,y?}也是一个独立集,它是I、I??、I??的所有邻居。由条件2,J∪{u,v,y?}在V?中,但它有三个邻居在V?中,这与条件3矛盾。

接下来我们证明V?不包含大小为3的独立集。如果V?包含独立集{u,v,w},那么由上一段,大小为4的任何邻居都不能在V?中。由于由条件3它必须在V?中有两个邻居,这些邻居(在对称意义下)必须是{u,v}和{u,w}。但是这两个集在V?中有{u}和{u,v,w}作为公共邻居,与条件4矛盾。

由上一段,V?中每个大小为2的独立集只能在V?中有大小为1的邻居,因此度数为2。设I是V?中大小为1的独立集。那么由条件3,I在V?中有两个邻居,它们的大小必须为2。如果I在V?中有邻居I',那么由条件3,I'的大小为2且在V?中有三个邻居。那么这三个邻居中有一个大小将不满足上一段的条件,导致矛盾。我们可以得出结论:如果V?中存在大小为2的独立集,那么它必须恰好与V?中的两个集相邻,这两个集的大小都为1;并且V?中每个大小为1的集也恰好有两个邻居,它们的大小都为2且都在V?中。换句话说,如果V?中存在大小为2的独立集,那么它必须位于??AR(G)的一个偶圈分量中。

这证明了对于??AR(G)中不构成偶圈的分量,V?只包含大小为1的独立集,从而完成了基础情形的证明。

**归纳步骤。** 设p>1,并假设对所有i2且I'在V_{p?2}中有p?1个邻居,每个的大小为p?2(由归纳假设)。由于I'只与|I'|=p?1个大小为|I'|?1=p?2的独立集相邻,I'的任何其他邻居的大小必须为|I'|+1=p。特别地,I的大小必须为p,这完成了归纳步骤。□

接下来需要研究当引理4.4的假设不满足时会发生什么,即当??AR(G)包含偶圈作为连通分量时。我们首先证明??AR(G)不连通当且仅当G可以分解为两个较小图的完全连接,这两个图的重新配置图恰好是??AR(G)的连通分量(引理4.5)。然后我们证明唯一使得重新配置图??AR(G)为偶圈C_{2i}(对某个i≥2)的图是C_i的补图(引理4.6)。将这些结果与本节的观察和引理4.4结合,就完成了TAR中k=1的情况。

**引理4.5** 设G是一个图,C是??AR(G)的一个连通分量。那么G是G??G?的完全连接,且C???AR(G?),??AR(G)?C???AR(G?)。

**证明** 设X?={v∈V(G)∣{v}∈V(C)},X?=V(G)?X?。在G中,由X?和X?诱导的图G?和G?必须完全连接,否则就会有一个独立集I={v?,v?},其中v?∈X?,v?∈X?。但I与{v?}∈C和{v?}?C都相邻,这与C是一个分量矛盾。

因此G?G??G?,因此G的每个独立集都是G?或G?的独立集,这说明??AR(G?)?C且??AR(G?)???AR(G)?C。□

**引理4.6** 设G是一个图,i≥2是整数。??AR(G)?C_{2i}当且仅当i≥4且G?C?_i。

**证明** (?) 图??AR(C?_i)有2i个顶点,分别对应C_i的顶点和在C_i中相邻的顶点对。(由于C_i,i≥4,不包含三角形,C?_i没有大小大于2的独立集。)C?_i中每个大小为1的独立集恰好有两个大小为2的邻居(即C_i的边),因此??AR(C?_i)?C_{2i}。

(?) 设G是一个图,使得??AR(G)?C_{2i};称这些顶点为{v?,…,v_{2i}}。注意到由于??AR(G)中每个顶点的度数都是2,G没有大小为3的独立集。此外,大小为1的独立集也有度数为2,意味着每个顶点与除两个顶点外的所有其他顶点相邻。由此推出每个顶点在G?中的度数为2,因此G?是若干圈的不相交并,记为C_{i?}∪?∪C_{i_p}。那么G是这些圈的补图的完全连接,这使得??AR(G)是C_{2i?},…,C_{2i_p}的不相交并。由于我们假设??AR(G)?C_{2i},我们必须有p=1,i_p=i,且G?C?_i。最后,G没有大小为3的独立集这一事实迫使i≥4。□

**4.3. k≥2的情形**

我们以独立集重构中k≥2时的否定结果来结束本节。我们从一个简单的观察开始。选择一个图H,其最大独立集的大小至多为k?1。对任意图G,设G'=G?H为G和H的完全连接。根据构造,G'中每个大小至少为k的独立集完全包含在G'中G的副本内,因此G和G'在使用至少k个标记时共享相同的重新配置图,无论采用何种范式。特别地,我们有以下推论。

**推论4.7** 对任意标记数k≥2,存在无限个图族具有相同的重新配置图?_kJ、?_kS和?_kAR。

因此,当k≥2时,没有希望从G的任何独立集重新配置图中确定G。一个自然的后续问题是:如果禁止这种特定构造,会发生什么,例如要求每当有完全连接G?G??G?时,G?和G?都必须包含大小为k的独立集。在这种情况下,G的重新配置图是G?和G?的重新配置图的不相交并。因此只需考虑连通的重新配置图。问题现在似乎困难得多,我们只解决了一个情形:无普邻顶点的图的Token Jumping中k=2的情况(普邻顶点是与其他所有顶点都相邻的顶点)。

观察到G中大小为2的独立集对应G的非边,我们有如果k=2,那么?_kJ(G)恰好是G的补图G?的线图。对于没有孤立顶点的图,图是连通的当且仅当其线图是连通的。因此如果假设?_kJ(G)是连通的,那么G?也是连通的(因为G没有普邻顶点)。因此,再次使用Whitney定理[8],我们推导出以下结果。

**推论4.8** 设G是一个无普邻顶点的图,且??J(G)是连通的。那么G可以从??J(G)确定,除非??J(G)是三角形K?且G?是K?或爪K?,?。

我们几乎不知道当k≥2时从?_kS(G)或?_kAR(G)确定图G的可能性,或者当k≥3时从?_kJ(G)确定G的可能性。如果只考虑特定图类,或者对重新配置图施加限制(如推论4.8中所做的),似乎这是可能的。

**问题4.9**
(a) 给定k≥2,对于哪些图类??,可以从?_kJ(G)、?_kS(G)或?_kAR(G)之一重构任何G∈???
(b) 给定k≥2,对于哪些图类??,如果所考虑的重新配置图是连通的,可以从?_kJ(G)、?_kS(G)或?_kAR(G)之一重构任何G∈???

Gaétan Berthe | Caroline Brosse | Brian Hearn | Jan van den Heuvel | Pierre Hoppenot | Théo Pierron
Clermont Auvergne大学,LIMOS,CNRS,法国克莱蒙费朗
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号