唯一可着色图

一个唯一 -可着色图 是一个色数 为 的图，使得每个 -着色都给出 的顶点相同的划分（Cartwright 和 Harary 1968；Harary 等人 1969；Ballobás 1978；Harary 1994，第 137-140 页；Chao 2001；Brešar 等人 2023）。等价地，一个色数为 的图是唯一可着色的当且仅当其顶点可以恰好以一种方式划分为 个独立顶点集。重要的是要注意，当考虑唯一性时，此定义不考虑图自同构群的作用，因此图中本身的任何对称性都被忽略（即，顶点被视为“固定”）。

唯一可着色图类的例子包括完全图 、连通 二分图、-部图和树。k-树是 -唯一可着色的 (Xu 1990)。

空图 (对于 ) 是唯一可着色的唯一非连通图。

Chartrand 和 Geller (1969) 证明不存在唯一 5-可着色的平面图，Fowler (1998) 将唯一 4-可着色的平面图定义为恰好是平面 3-树（参见 Brešar 等人 2023，他们省略了对 3-树的“平面”限制）。

具有 , 2, ... 个节点的简单唯一可着色图的数量是 1, 2, 3, 6, 11, 35, 134, 1183, 21319, ... (OEIS A369223)。

唯一 -可着色图是 -连通的 (Chartrand 和 Geller 1969)。

唯一 -可着色图满足

(1)

其中 是最小顶点度 (Brešar 等人 2023)。

Ballobás (1978) 表明，对于具有 个 个顶点和 条边的图 而言，使其成为唯一 -可着色的一个充分条件是不等式

(2)

成立。然而，该条件不是必要的，即存在唯一可着色但该不等式不成立的图。

Truszczyński (1984) 和 Xu (1990) 给出了唯一可着色的必要条件，即满足不等式

(3)

因此，如果该不等式不成立，则图不是唯一可着色的；而如果该不等式成立，则图可能是也可能不是唯一可着色的。

Chao (2001) 证明，对于每个整数 ，都存在具有 和 个顶点的唯一 -可着色图，并且存在两个具有 和 个顶点的唯一 -可着色图，它们是色等价的。

Harary et al. (1969) 和 Harary (1994，封面和第 139 页) 给出了两个被错误地识别为唯一可着色的图（从上面插图中顶点按颜色的不同划分的存在可以看出）。第一个在 Harary et al. (1970) 中通过在左侧、顶部和右侧添加边进行了更正。

唯一可着色的另一个定义认为，如果存在图自同构和颜色交换的组合，将一种着色转换为另一种着色，则两种着色是等价的（Osterweil 1974，Chia 1996，Brešar et al. 2023）。为了将这种情况与更常用的定义区分开来，在更常用的定义中，图自同构群的作用已被删除，Chia (1996) 使用术语“在自同构群作用下唯一可着色”，而 Brešar et al. (2023) 将此类图称为 -同构唯一。一些图可能仅基于图的对称性，在其自同构群的作用下是唯一可着色的，即，图自同构群本身的作用是以所有可能的方式交换颜色，而无需显式考虑颜色交换。示例包括 Sierpiński gasket 图及其在奇数维度上的推广（D. Knuth，私人通信，2022 年 5 月 1 日）。