唯一可著色圖

一個唯一 -可著色圖 是一個色數 為 的圖，使得每個 -著色都給出 的頂點相同的劃分（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 日）。