圖同態

數學分支圖論中，**圖同態**（英語：graph homomorphism）是兩幅圖之間保結構的對映。具體而言，該對映將某圖的各頂點映至另一圖的頂點，且若兩頂點相鄰，則其像仍然相鄰。

同態是若干種圖著色概念的推廣，適用於表達一類重要的約束滿足問題，如排程、頻段分配問題。同態可以複合，為全體圖組成的類賦予豐富的代數結構：其上的預序關係、分配格結構、範疇結構（分為無向圖範疇與有向圖範疇兩種）。欲尋找任意兩圖間的同態，而無額外條件，則現時所知的計算複雜度高得不切實際，但對於某些特定類別的圖，已知有多項式時間演算法。此類問題易解與否，兩者的分野，是活躍的研究方向。

## 定義

本條目中，除非另有聲明，否則「圖」皆為有限無向圖，允許自環，但無重邊（兩點間連多於一條邊）。自 $G=(V(G),E(G))$ 至另一圖 $H=(V(H),E(H))$ 的**圖同態** $f$ ，記作

　
: $f:G\to H,$

是頂點集 $V(G)$ 至 $V(H)$ 的函式，其將 $G$ 每條邊的兩端分別映至 $H$ 某邊的兩端。以符號表示：對 $V(G)$ 中每對頂點 $u,v$ ，若 $\{u,v\}\in E(G)$ ，則 $\{f(u),f(v)\}\in E(H)$ 。若存在 $G$ 至 $H$ 的同態，則稱 $G$ **同態於**（homomorphic to） $H$ ，或**可染 $H$ 色**（ $H$ -colourable），常簡記為：

　
: $G\to H.$

上述定義可引伸至有向圖，此時， $f:G\to H$ 為同態的條件是， $G$ 中每條有向邊 $(u,v)$ 的像 $(f(u),f(v))$ ，仍是 $H$ 的有向邊。

自 $G$ 至 $H$ 有單同態（將不同頂點映至不同頂點），若且唯若 $G$ 為 $H$ 的子圖。若同態 $f:G\to H$ 為對射（兩圖頂點集的一一對應），且其逆 $f^{-1}$ 亦是圖同態，則 $f$ 為圖同構。

圖的覆疊對映是一類特殊的圖同態，相當於將圖視為拓撲空間時，拓撲學上的覆疊對映，其定義及性質亦是類似：圖覆疊是滿同態（即作為對應域的圖，其每個頂點皆為定義域某頂點的像），且局部為對射，即若限制到每個頂點的鄰域，則為對射。舉例，圖的典範雙重覆疊，是將每點 $v$ 分裂為 $v_{0},v_{1}$ 兩點，並將原圖每條邊 $uv$ 換成交叉的兩條邊 $u_{0}v_{1}$ 、 $u_{1}v_{0}$ 。如此，可以定義函式將 $v_{0}$ 和 $v_{1}$ 皆映至 $v$ ，既是圖同態，也是覆疊對映。

圖同胚是另一個概念，不一定是同態。粗略而言，同胚要求是單射，但不必將邊映至邊，允許映至路徑。圖子式的要求更鬆。

### 核與回縮

若兩幅圖 $G$ 和 $H$ 有同態 $G\to H$ 及 $H\to G$ ，則稱兩者**同態等價**（homomorphically equivalent）。該些對映不必單，也不必滿。例如，完全二部圖 $K_{2,2}$ 與 $K_{3,3}$ 同態等價，因為可將 $K_{2,2}$ 左部兩個頂點映到 $K_{3,3}$ 左部同一個頂點，其右部的兩個頂點映到 $K_{3,3}$ 右部一個頂點，同樣有 $K_{3,3}\to K_{2,2}$ 的同態。

**收縮對映**（retraction）是自圖 $G$ 至其子圖 $H$ 的同態 $r$ ，且對 $H$ 中每個頂點 $v$ 有 $r(v)=v$ 。若有此種對映，則 $H$ 稱為 $G$ 的**收縮核**（retract）。

**核圖**（core）沒有到任何真子圖的同態。亦可等價定義成無法收縮到任何真子圖的圖。每幅圖 $G$ 皆同態等價於唯一的核圖（不辨同構之別），稱為 **$G$ 的核**（the core of $G$ ）。此結論對無窮圖不一定成立，但對（有限的）有向圖可以照套用同樣的定義，每幅有向圖同態等價於唯一的的核圖。圖（或有向圖）的核，必為原圖某個收縮核，以及某個匯出子圖。

舉例，完全圖 $K_{n}$ 及奇環（奇數條邊的迴圈圖）皆屬核圖。若 $G$ 可染三色，且有三角形（即子圖 $K_{3}$ ），則 $G$ 同態等價於 $K_{3}$ ，原因是 $G$ 的三染色，下節將說明相當於同態 $G\to K_{3}$ ，且另一方面，任意子圖皆有同態嵌入到 $G$ ，故有 $K_{3}\to G$ 。如此，證畢 $K_{3}$ 為所有此種 $G$ 的核。與之相似，每幅非空二部圖（有至少一條邊）皆等價於 $K_{2}$ 。

## 與染色的關聯

對正整數 $k$ ，圖 $G$ 的 $k$ 染色是將每個頂點塗 $k$ 色之一，使每條邊的兩端都不同色。此種染色，與自 $G$ 至完全圖 $K_{k}$ 的同態，兩類物件一一對應，因為 $K_{k}$ 的各頂點對應 $k$ 種色，且若 $c_{1},c_{2}$ 為顏色，則其於圖 $K_{k}$ 相鄰若且唯若 $c_{1}\neq c_{2}$ 。於是，某函式是 $G$ 至 $K_{k}$ 的同態，若且唯若該函式將 $G$ 中相鄰的頂點映至不同顏色（即 $k$ 染色的定義）。換言之， $G$ 可染 $k$ 色等價於可染 $K_{k}$ 色。

若有同態 $G\to H$ 及 $H\to K_{k}$ ，則兩者複合可得同態 $G\to K_{k}$ 。所以，若 $H$ 可染 $k$ 色，且有同態 $G\to H$ ，則 $G$ 同樣可染 $k$ 色。因此， $G\to H$ 推出 $\chi (G)\leq \chi (H)$ ，其中 $\chi $ 表示圖的色數。

### 變式

其他同態亦可視作特殊的染色。給定圖 $H$ ，其頂點視為可用的顏色，每條邊表示某兩色「可相容」，則 $G$ 的 $H$ 染色就是將相鄰頂點染成相容顏色的方案。此框架可容納許多圖染色的概念，將其表述為射向各類圖的同態。舉例如下：

* 循環染色可定義為至循環完全圖的同態，從而推廣一般的染色，定義「分數」色數。
* 分數染色與 _b_ 重染色可定義成射向克內澤爾圖的同態。
* _T_ 染色的可用色集為自然數集 $\mathbb {N} $ ，但另有給定某子集 $T\subseteq \mathbb {N} $ ，禁止相鄰頂點所染顏色之差屬於 $T$ 。此種染色對應往某幅無窮圖的同態。
* 有向染色除禁止相鄰頂點同色外，還限制不同顏色之間的所有邊皆同向（例如由藍至紅）。此為映向有向圖的同態。
* L (2,1) 染色以數表示顏色，要求距離為 1（相鄰）的頂點所染顏色之差至少為 2，而距離為 2 的頂點染色之差至少為 1。換言之，此為射向路圖 $P_{n}$ 之補的同態，且要求局部為單射，即在每個頂點的鄰域上為單射。

### 無長路徑的定向

圖同態與圖定向也有關。無向圖 $G$ 的定向是賦予每邊一個方向（二選一），所得的有向圖。同一幅無向圖可以有多種不同的定向。舉例，完全圖 $K_{k}$ 可定向成「遞移循環賽圖」 ${\overrightarrow {T_{k}}}$ ，其頂點為 $1,2,\ldots ,k$ ，對所有 $i<j$ 有（有向）邊自 $i$ 指向 $j$ 。給定 $G$ 的定向與 $H$ 的定向之間的同態，忘掉定向即得本來無向圖之間的同態。另一方面，給定無向圖同態 $G\to H$ ， $H$ 任何定向 ${\overrightarrow {H}}$ 可以拉回到 $G$ 的定向 ${\overrightarrow {G}}$ ，使原同態亦是 ${\overrightarrow {G}}\to {\overrightarrow {H}}$ 的有向圖同態。綜上，無向圖 $G$ 可染 $k$ 色（即有同態至 $K_{k}$ ），若且唯若 $G$ 有某定向，具有至 ${\overrightarrow {T_{k}}}$ 的同態。

有定理流傳，對每個 $k$ ，有向圖 $G$ 有同態至 ${\overrightarrow {T_{k}}}$ ，若且唯若 $k+1$ 個頂點的有向路徑圖 ${\overrightarrow {P_{k+1}}}$ 無同態至 $G$ 。

因此，某圖可 $k$ 染色，若且唯若其有某定向，不容任何自 ${\overrightarrow {P_{k+1}}}$ 至該定向的同態。此命題可加強成

> 
> 高洛伊 - 哈塞 - 羅伊 - 維塔韋爾定理：某圖可 $k$ 染色，若且唯若該圖有某定向，其中無長為 $k$ 的有向路徑（即 ${\overrightarrow {P_{k+1}}}$ 作為子圖）。
> 
> 

與前一命題的分別在於，自 ${\overrightarrow {P_{k+1}}}$ 至某圖的同態允許將兩頂點映至同處，但「長為 $k$ 的有向路徑」不允許重複頂點。

## 與約束滿足問題的關聯

### 範例

某些排程問題可用圖同態建模。設學校已知各學生所選科目，要編排今學期各專題討論班的時間，使同一學生所選的討論班時間不致太近。考慮圖 $G$ 以各科為頂點，若兩科有共同學生則連邊，而圖 $H$ 以各課節為頂點，若兩個時段隔足夠遠則連邊。舉例若限制時間表須每週循環，且每個學生所選的討論班須相隔一日，則對應的 $H$ 是環 $C_{7}$ 的補圖。如此， $G\to H$ 的圖同態，就是討論班對應到課節的合適方案。欲添加額外條件，如禁止學生同時於週五與週一有討論班，衹需從 $H$ 刪掉相應的邊。

無線電的頻段分配問題簡述如下：無線網路中，有若干發訊機，要為每部機組態一個頻率，供其發訊。為免干擾，地理位置較近的發訊機應選用相差較遠的頻率。若將條件中「地理較近」與「頻率較遠」簡化至非黑即白，則合適的分配方案又可視為圖同態 $G\to H$ 。圖 $G$ 的頂點為各發訊機，邊表示兩機地理上接近；圖 $H$ 以各頻段為頂點，邊則表示兩頻段相隔夠遠。雖然此模型甚為簡化，但是尚有保留一點彈性：若有兩機相隔較遠，但仍因地形導致可能干擾，則在 $G$ 中加邊即可。反之，若有兩機永不在同一時段發訊，則不論其地理位置是否靠近，皆可從 $G$ 中刪去該邊。同樣，或許有某些頻率相差頗遠，但是互為諧波，導致干擾，則將該邊自 $H$ 移除即可

前述模型經簡化，若要實際應用，許多問題仍待解決。約束滿足問題是圖同態問題的推廣，能表達更多種條件（例如個體偏好，或重複分配次數有上限），從而建立更實際的數學模型。

### 抽象觀點

數理邏輯或泛代數中，圖與有向圖屬關係結構的特例，即集合配備若干關係。有向圖就是基集（頂點集）之上有獨一個二元關係（鄰接關係）。如是觀之，圖作為關係結構的同態，按抽象代數的同態定義，等同於本文的圖同態。一般而言，欲尋找自某關係結構至另一關係結構的同態，屬於約束滿足問題（constraint satisfaction problem, CSP）。圖的特例可作為第一步，幫助理解更複雜的 CSP。許多尋找圖同構的演算法，包括回溯、約束傳播、局部搜尋，通用於各種 CSP。

給定圖 $G$ 、 $H$ ，問是否有同態 $G\to H$ ，相當於僅得一類約束的 CSP 實例：CSP 的「變數」是 $G$ 的頂點，每個變數的「域」（可取值的範圍）是 $H$ 的頂點集。「賦值」是一個函式，將逐個變數映至域的元素，即函式 $f:V(G)\to V(H)$ 。 $G$ 的每條邊（或有向邊） $(u,v)$ 對應一個「約束」 $((u,v),E(H))$ ，限制賦值函式將邊 $(u,v)$ 映至關係 $E(H)$ 中，即映至 $H$ 的某邊。CSP 的「解」是滿足全體約束的賦值，故前述 CSP 的解正是自 $G$ 至 $H$ 的同態。

## 同態的結構

同態的複合仍是同態，故可知圖的 $\to $ 關係具遞移性，又顯然自反，所以其為圖之間的預序。同態等價意義下，記 $G$ 所屬等價類為 $[G]$ ，每個等價類有唯一的核圖為其代表。關係 $\to $ 定義該些等價類之間的偏序，即同態等價類構成一個偏序集。

以 $G<H$ 表示 $G$ 有同態至 $H$ ，但反之則不然。如此定義的序 $<$ 稠密，即對任意（無向）圖 $G,H$ ，若 $G<H$ ，則存在第三幅圖 $K$ 使 $G<K<H$ ，除非是平凡反例 $G=K_{0}$ 或 $G=K_{1}$ 。例如，任意兩幅整數階完全圖（除 $K_{0},K_{1},K_{2}$ 外）之間，必有無窮多幅環狀完全圖，相當於整階數之間的有理數階數。

同態等價類的偏序集是分配格，併 $[G]\lor [H]$ 是互斥併 $[G\sqcup H]$ ，而交 $[G]\land [H]$ 是圖張量積 $[G\times H]$ ，其定義不取決於等價類中所選的代表 $G,H$ 。此格中，併不可約元正好是連通圖，證明方式是留意同態衹會將連通圖映到目標的一個連通分支中。交不可約元正好是積性圖（multiplicative graphs），此種圖 $K$ 的特性是，若乘積 $G\times H$ 有同態至 $H$ ，則 $G$ 或 $H$ 兩者之一有同態至 $H$ 。如何識別積性圖是赫德米猜想的關鍵。

圖與同態還組成範疇：圖是物件，而同態是態射。範疇的始物件是空圖 $K_{0}$ ，終物件有一個頂點和一個自環。圖張量積是範疇論積，指數圖是該範疇的指數物件。換言之，自 $G\times H\to K$ 的同態與 $H\to K^{G}$ 的同態自然地一一對應。由於對任意圖 $G,H$ ，張量積 $G\times H$ 與冪 $H^{G}$ 總有定義，圖範疇是笛卡兒閉範疇。同理，同態等價類組成的格實際上是海廷代數：按海廷代數的語言，前述的積稱為交運算 $\land $ ，而前述的指數運算稱為蘊涵 $\Rightarrow $ 。

對於有向圖，適用同樣的定義。同樣有 $\to $ 是有向圖同態等價類之間的偏序，其與無向圖等價類的偏序 $\to $ 有別，但後者是前者的子序，因為無向圖亦可視為有向圖，衹是其中每條有向邊 $(u,v)$ 皆與其反向 $(v,u)$ 成對出現。換言之，無向圖同態的定義，與雙向有向圖的同態並無區別。有向圖的 $\to $ 序仍是分配格和海延代數，交與併的定義亦同上，但分別在於，該序並不稠密。亦有以有向圖為物件、同態為態射的範疇，照樣笛卡兒閉。

### 不可比圖

同態預序下，許多圖不可比較。兩幅不可比圖（incomparable graphs）之間，並無自任意一幅至另一幅的同態。欲構造此種圖，可考慮圖的奇圍長，即最短的奇環長度。奇圍長可等價地說成最小的奇數 $g$ ，使 $g$ 個頂點的迴圈圖 $C_{g}$ 有同態至 $G$ 。由此定義，若 $G\to H$ ，則 $G$ 的奇圍長大於或等於 $H$ 的奇圍長。

另一方面，前節已證若 $G\to H$ ，則 $G$ 的色數小於或等於 $H$ 的色數。所以，若 $G$ 的奇圍長及色數皆嚴格大於 $H$ ，則 $G$ 和 $H$ 不可比較。
舉例，格勒奇圖色數為 $4$ ，且無三角形（圍長 $4$ ，奇圍長 $5$ ），所以與三角形 $K_{3}$ 不可比。

有幾類圖的奇圍長和色數可取任意大，如克內澤爾圖與廣義梅切爾斯基圖。如此一類圖，若使其兩參數同時遞增，排成一列，則有無窮多幅不可比圖（同態預序下的反鏈）。
同態預序稠密等其他性質，亦可利用此類圖證明。此外，可構造同時具大色數和大圍長（不僅是奇圍長）的圖，但較複雜，見圍長 (圖論) § 圍長與圖染色。

有向圖之中，更易找到不可比圖。例如，考慮有向環 ${\overrightarrow {C_{n}}}$ ，頂點為 $1,2,\ldots ,n$ ，有向邊自 $i$ 至 $i+1$ （對 $i=1,2,\ldots ,n-1$ 各一），及自 $n$ 至 $1$ 。對於 $n,k\geq 3$ ， ${\overrightarrow {C_{n}}}$ 至 ${\overrightarrow {C_{k}}}$ 有同態若且唯若 $n$ 為 $k$ 的倍數。所以，當 $p$ 取質數值時， ${\overrightarrow {C_{p}}}$ 兩兩不可比。

## 計算複雜度

圖同態問題是給定一對圖 $(G,H)$ ，求自 $G$ 至 $H$ 的圖同態。對應的決定性問題問是否存在此種解。一般情況下，即詢問的實例 $(G,H)$ 不受額外限制的情況下，此決定性問題為 NP 完全。若限制詢問的範圍，衹限從某類圖中選出 $G$ 或 $H$ ，則可得多種不同的問題，其中有些較易求解。限制左邊 $G$ 和限制右邊 $H$ 相比，適用的方法相去甚遠，但兩者似乎有一共同特點：難易情況之間似乎有明確的分界，此分界或者已獲證，或有論文猜想如此。

### 至給定圖的同態

圖同態問題若固定右邊的圖 $H$ 不變，則稱為染 $H$ 色問題。 $H$ 為完全圖 $K_{k}$ 時，化成染 _k_ 色問題，在 $k=0,1,2$ 時，可於多項式時間內求解，但其餘情況則是 NP 完全。 $k=2$ 的情況相當於問圖 $G$ 可否染 $K_{2}$ 色，即是否二部圖，此問題可在線性時間內求解。更一般地，衹要 $H$ 是二部圖就有同一結論：可染 $H$ 色等價於可染 $K_{2}$ 色，即可染二色，故此種情況同樣易判斷。可染 $K_{0}$ 色和可染 $K_{1}$ 色分別等價於無頂點和無邊，亦易判斷。帕沃爾・黑爾和雅羅斯拉夫・內舍特日爾證明，對無向圖而言，無其他情況可馴順：

> 
> （黑爾 - 內舍特日爾定理，1990 年）若 $H$ 為二部圖，則染 $H$ 色問題屬於 P，但其餘情況則為 NP 完全。
> 
> 

上述定理又稱為無向圖同態的「對分定理」（dichotomy theorem），因為將染 $H$ 色問題分成 NP 完全與 P 兩類，而無居中情況。有向圖情況較複雜，此時問題等價於刻畫看似更一般的約束滿足問題的複雜度：有向圖的染 $H$ 色問題，與允許各種約束條件的 CSP 相比，同樣多姿多彩，而不失一般性。嚴格而言，定義（有限）約束語言（constraint language，或稱模板 template） $\Gamma $ 為一個有限的取值域，其上配備有限多種關係，然後以 ${\mathsf {CSP}}(\Gamma )$ 表示約束衹能選自 $\Gamma $ 的一類約束滿足問題，則有以下定理：

> 
> （費德、瓦迪，1998 年）對任意約束語言 $\Gamma $ ，必有某幅有向圖 $H$ ，使 ${\mathsf {CSP}}(\Gamma )$ 在多項式時間歸約意義下等價於染 $H$ 色問題。
> 
> 

直觀理解，定理意味著任何演算法技巧或複雜度結論，若適用於一般有向圖 $H$ 的染 $H$ 色問題，則可套用至一般 CSP。考慮將黑爾 - 內舍特日爾定理擴展至有向圖。由上述定理，該推廣等價於有關 CSP 對分的費德 - 瓦迪猜想（又稱 CSP 猜想、對分猜想），即斷言對任意約束語言 $\Gamma $ ， ${\mathsf {CSP}}(\Gamma )$ 或屬 NP 完全，或屬 P。此猜想於 2017 年由德米特里・祖克（Dmitry Zhuk）與安德烈・布拉托夫（Andrei Bulatov）分別獨立證出，故有以下推論：

> 
> （布拉托夫 2017 年；祖克 2017 年）給定 $H$ 時，有向圖的染 $H$ 色問題或屬 P，或屬 NP 完全。
> 
> 

### 自給定族的同態

若左輸入 $G$ 為給定，則圖同態問題有暴力解法，即窮舉 $G$ 的各個頂點在 $H$ 中的像，複雜度僅為 ${\mathcal {O}}\left(|V(H)|^{|V(G)|}\right)$ ，已是輸入 $H$ 的多項式函式。換言之，限制 $G$ 的大小時，問題顯然屬 P，但仍可改為研究另一課題：除大小之外，是否其他限制可施加於 $G$ ，使圖同態問題可於多項式時間內求解？

研究表明，關鍵性質是樹闊，此參數衡量一幅圖有多似一棵樹。若 $G$ 的樹闊至多為 $k$ ，而 $H$ 為任意圖，則利用標準的動態規劃方法，可於 $|V(H)|^{{\mathcal {O}}(k)}$ 時間內求解圖同態問題。實際甚至衹需假設 $G$ 的核的樹闊不逾 $k$ ，而無需知道其核為何。

該 $|V(H)|^{{\mathcal {O}}(k)}$ 演算法中，複雜度的指數可能無法再壓低太多：若指數時間假設（ETH）為真，則不存在時間複雜度為 $|V(H)|^{o(\mathrm {tw} (G)/\log \mathrm {tw} (G))}$ 的演算法。即使限制 $G$ 衹能取值為某一族圖，衹要該族圖的樹闊無上界，則仍有同樣結論。同樣假設下，幾乎沒有其他性質使問題可於多項式時間內求解，具體含義如下：

> 
> （格羅厄）假定 ETH，並給定由圖組成的可計算族 ${\mathcal {G}}$ 。考慮輸入為 $(G,H)$ ，且 $G\in {\mathcal {G}}$ 的圖同態問題。此問題屬 P 若且唯若 ${\mathcal {G}}$ 中各圖之核的樹闊有界。
> 
> 

或考慮有所取捨，允許複雜度高度依賴 $G$ ，換取複雜度與 $H$ 的關係僅為固定的多項式。與前段類似，若 $G$ 的取值範圍中，核的樹闊有界，則此目標可以實現，但若 $G$ 的取值範圍不滿足該條件，則無法達成。利用帶參數複雜度術語，上述成果可覆述為： ${\mathcal {G}}$ 中的同態問題，以 $G$ 的邊數為參數，呈現對分現象。若 ${\mathcal {G}}$ 中各圖之核的樹闊有上界，則該問題為固定參數可馴順，否則為 W[1]完全。

同一命題對其他關係結構亦成立。換言之，其適用於一般的約束滿足問題，不過需要限制各項約束涉及的變數數有上界，即關係的元數有上界（以圖為例，僅得元數為 2 的關係）。此時，關鍵參數為原始約束圖的樹闊。

## 參見

* 圖論術語
* 同態，其他代數結構的同一概念
* 圖重寫
* 中位圖，可定義成超立方圖的收縮核
* 西多連科猜想

## 註

## 參考資料

### 一般書目、解說

* Cameron, P. Graph Homomorphisms, Combinatorics Study Group Notes [圖同態，組合研習小組講義] (PDF). 2006 [2022-02-12]. （原始內容 (PDF) 存檔於 2021-05-07） （英語）.
* Hell, Pavol; Nešetřil, Jaroslav. Graphs and Homomorphisms [圖與同態]. Oxford Lecture Series in Mathematics and Its Applications **28**. Oxford University Press. 2004 [2022-02-12]. ISBN0-19-852817-5. （原始內容存檔於 2021-05-06） （英語）.
* Hahn, G.; Tardif, C. Graph homomorphisms: structure and symmetry [圖同態：結構與對稱]. Graph Symmetry: Algebraic Methods and Applications [圖對稱：代數方法及應用] (PDF). Springer. 1997: 107–166 [2022-02-12]. doi:10.1007/978-94-015-8937-6\_4. （原始內容 (PDF) 存檔於 2021-07-11） （英語）.
* Godsil, C.; Royle, G. 6. Homomorphisms [6、同態]. Algebraic Graph Theory [代數圖論]. Graduate Texts in Mathematics **207**. Springer–Verlag New York. 2001. ISBN 978-1-4613-0163-9. doi:10.1007/978-1-4613-0163-9 （英語）.

### 約束滿足、泛代數

* Bodirsky, M. Graph Homomorphisms and Universal Algebra, Course Notes [圖同態與泛代數，講義] (PDF). 2007 [2022-02-12]. （原始內容 (PDF) 存檔於 2022-05-01） （英語）.
* Hell, Pavol; Nešetřil, Jaroslav. Colouring, constraint satisfaction, and complexity [染色、約束滿足、複雜度] (PDF). Computer Science Review. 2008, **2** (3): 143–163 [2022-02-12]. doi:10.1016/j.cosrev.2008.10.003. （原始內容 (PDF) 存檔於 2017-07-06） （英語）.

### 格論、範疇論

* Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. Graphs of morphisms of graphs [圖態射之圖]. Electronic Journal of Combinatorics. 2008, **15** (1): A1 [2022-02-12]. doi:10.37236/919 . （原始內容存檔於 2021-07-11） （英語）.
* Gray, C. T. The Digraph Lattice [有向圖之格] (PDF). 2014 [2022-02-12]. （原始內容 (PDF) 存檔於 2022-01-20） （英語）.