图同态

数学分支图论中，图同态（英语：graph homomorphism）是两幅图之间保结构的映射。具体而言，该映射将某图的各顶点映至另一图的顶点，且若两顶点相邻，则其像仍然相邻。

同态是若干种图着色概念的推广，适用于表达一类重要的约束满足问题，如排程、频段分配（英语：frequency assignment）问题。^[1]同态可以复合，为全体图组成的类赋予丰富的代数结构：其上的预序关系、分配格结构、范畴结构（分为无向图范畴与有向图范畴两种）。^[2]欲寻找任意两图间的同态，而无额外条件，则现时所知的计算复杂度（英语：computational complexity）高得不切实际，但对于某些特定类别的图，已知有多项式时间算法。此类问题易解与否，两者的分野，是活跃的研究方向。^[3]

定义

本条目中，除非另有声明，否则“图”皆为有限无向图，允许自环，但无重边（两点间连多于一条边）。自 $G=(V(G),E(G))$ 至另一图 $H=(V(H),E(H))$ 的图同态^[4] $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$ 为图同构。^[5]

图的覆叠映射（英语：Covering graph）是一类特殊的图同态，相当于将图视为拓扑空间（英语：Graph (topology)）时，拓扑学上的覆叠映射，其定义及性质亦是类似：^[6]图覆叠是满同态（即作为陪域的图，其每个顶点皆为定义域某顶点的像），且局部为双射，即若限制到每个顶点的邻域（英语：neighbourhood (graph theory)），则为双射。举例，图的典范双重复叠（英语：bipartite double cover），是将每点 $v$ 分裂为 $v_{0},v_{1}$ 两点，并将原图每条边 $uv$ 换成交叉的两条边 $u_{0}v_{1}$ 、 $u_{1}v_{0}$ 。如此，可以定义函数将 $v_{0}$ 和 $v_{1}$ 皆映至 $v$ ，既是图同态，也是覆叠映射。

图同胚是另一个概念，不一定是同态。粗略而言，同胚要求是单射，但不必将边映至边，允许映至路径。图子式的要求更松。

核与回缩

K₇，七个顶点的完全图，一种核图

若两幅图 $G$ 和 $H$ 有同态 $G\to H$ 及 $H\to G$ ，则称两者同态等价（homomorphically equivalent）。^[4]该些映射不必单，也不必满。例如，完全二部图 $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）。^[7]

核图（core）没有到任何真子图的同态。亦可等价定义成无法收缩到任何真子图的图。^[8]每幅图 $G$ 皆同态等价于唯一的核图（不辨同构之别），称为 $G$ 的核（the core of $G$ ）。^[9]此结论对无穷图不一定成立^[10]，但对（有限的）有向图可以照套用同样的定义，每幅有向图同态等价于唯一的核图。图（或有向图）的核，必为原图某个收缩核，以及某个导出子图。^[7]

举例，完全图 $K_{n}$ 及奇环（奇数条边的循环图）皆属核图。若 $G$ 可染三色，且有三角形（即子图 $K_{3}$ ），则 $G$ 同态等价于 $K_{3}$ ，原因是 $G$ 的三染色，下节将说明相当于同态 $G\to K_{3}$ ，且另一方面，任意子图皆有同态嵌入到 $G$ ，故有 $K_{3}\to G$ 。如此，证毕 $K_{3}$ 为所有此种 $G$ 的核。与之相似，每幅非空二部图（有至少一条边）皆等价于 $K_{2}$ 。^[11]

与染色的关联

对正整数 $k$ ，图 $G$ 的 $k$ 染色是将每个顶点涂 $k$ 色之一，使每条边的两端都不同色。此种染色，与自 $G$ 至完全图 $K_{k}$ 的同态，两类物件一一对应^[12]，因为 $K_{k}$ 的各顶点对应 $k$ 种色，且若 $c_{1},c_{2}$ 为颜色，则其于图 $K_{k}$ 相邻当且仅当 $c_{1}\neq c_{2}$ 。于是，某函数是 $G$ 至 $K_{k}$ 的同态，当且仅当该函数将 $G$ 中相邻的顶点映至不同颜色（即 $k$ 染色的定义）。换言之， $G$ 可染 $k$ 色等价于可染 $K_{k}$ 色。^[12]

若有同态 $G\to H$ 及 $H\to K_{k}$ ，则两者复合可得同态 $G\to K_{k}$ 。^[13]所以，若 $H$ 可染 $k$ 色，且有同态 $G\to H$ ，则 $G$ 同样可染 $k$ 色。因此， $G\to H$ 推出 $\chi (G)\leq \chi (H)$ ，其中 $\chi$ 表示图的色数^{[注 1]}。^[14]

变式

其他同态亦可视作特殊的染色。给定图 $H$ ，其顶点视为可用的颜色，每条边表示某两色“可兼容”，则 $G$ 的 $H$ 染色就是将相邻顶点染成相容颜色的方案。此框架可容纳许多图染色的概念，将其表述为射向各类图的同态。举例如下：

循环染色（英语：Circular coloring）可定义为至循环完全图（英语：circular clique）^{[注 2]}的同态，从而推广一般的染色，定义“分数”色数。^[15]
分数染色（英语：Fractional coloring）与b重染色（英语：Fractional coloring）可定义成射向克内泽尔图（英语：Kneser graph）的同态。^[16]
T染色（英语：T-coloring）的可用色集为自然数集 $\mathbb {N}$ ，但另有给定某子集 $T\subseteq \mathbb {N}$ ，禁止相邻顶点所染颜色之差属于 $T$ 。此种染色对应往某幅无穷图的同态。^[17]
有向染色（英语：oriented coloring）除禁止相邻顶点同色外，还限制不同颜色之间的所有边皆同向（例如由蓝至红）。此为映向有向图（英语：oriented graph）的同态。^[18]
L(2,1)染色（英语：L(2,1)-coloring）以数表示颜色，要求距离为1（相邻）的顶点所染颜色之差至少为2，而距离为2的顶点染色之差至少为1。换言之，此为射向路图 $P_{n}$ 之补的同态，且要求局部为单射，即在每个顶点的邻域上为单射。^[19]

无长路径的定向

图同态与图定向（英语：Orientation (graph theory)）也有关。无向图 $G$ 的定向是赋予每边一个方向（二选一），所得的有向图。同一幅无向图可以有多种不同的定向。举例，完全图 $K_{k}$ 可定向成“递移循环赛图（英语：Tournament (graph theory)）” ${\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}}}$ 的同态。^[20]

有定理流传^{[注 3]}，对每个 $k$ ，有向图 $G$ 有同态至 ${\overrightarrow {T_{k}}}$ ，当且仅当 $k+1$ 个顶点的有向路径图（英语：path graph） ${\overrightarrow {P_{k+1}}}$ ^{[注 4]}无同态至 $G$ 。^[21]

因此，某图可 $k$ 染色，当且仅当其有某定向，不容任何自 ${\overrightarrow {P_{k+1}}}$ 至该定向的同态。此命题可加强成

高洛伊-哈塞-罗伊-维塔韦尔定理（英语：Gallai–Hasse–Roy–Vitaver theorem）：某图可 $k$ 染色，当且仅当该图有某定向，其中无长为 $k$ 的有向路径（即 ${\overrightarrow {P_{k+1}}}$ 作为子图）。

与前一命题的分别在于，自 ${\overrightarrow {P_{k+1}}}$ 至某图的同态允许将两顶点映至同处，但“长为 $k$ 的有向路径”不允许重复顶点。

与约束满足问题的关联

范例

图

H

，表示一周中不相邻的日子，同构于环

C_{7}

的补图，亦同构于环状团（英语：circular clique）

K_{7/2}

某些排程问题可用图同态建模。^[22]^[23]设学校已知各学生所选科目，要编排今学期各专题讨论班的时间，使同一学生所选的讨论班时间不致太近。考虑图 $G$ 以各科为顶点，若两科有共同学生则连边，而图 $H$ 以各课节为顶点，若两个时段隔足够远则连边。举例若限制时间表须每周循环，且每个学生所选的讨论班须相隔一日，则对应的 $H$ 是环 $C_{7}$ 的补图。如此， $G\to H$ 的图同态，就是讨论班对应到课节的合适方案。^[22]欲添加额外条件，如禁止学生同时于周五与周一有讨论班，衹需从 $H$ 删掉相应的边。

无线电的频段分配（英语：frequency allocation）问题简述如下：无线网络中，有若干发讯机，要为每部机配置一个频率，供其发讯。为免干扰，地理位置较近的发讯机应选用相差较远的频率。若将条件中“地理较近”与“频率较远”简化至非黑即白，则合适的分配方案又可视为图同态 $G\to H$ 。图 $G$ 的顶点为各发讯机，边表示两机地理上接近；图 $H$ 以各频段为顶点，边则表示两频段相隔够远。虽然此模型甚为简化，但是尚有保留一点弹性：若有两机相隔较远，但仍因地形导致可能干扰，则在 $G$ 中加边即可。反之，若有两机永不在同一时段发讯，则不论其地理位置是否靠近，皆可从 $G$ 中删去该边。同样，或许有某些频率相差颇远，但是互为谐波，导致干扰，则将该边自 $H$ 移除即可^[24]

前述模型经简化，若要实际应用，许多问题仍待解决。^[25]约束满足问题是图同态问题的推广，能表达更多种条件（例如个体偏好，或重复分配次数有上限），从而建立更实际的数学模型。

抽象观点

数理逻辑或泛代数中，图与有向图属关系结构的特例，即集合配备若干关系。有向图就是基集（顶点集）之上有独一个二元关系（邻接关系）。^[26]^[3]如是观之，图作为关系结构的同态，按抽象代数的同态定义，等同于本文的图同态。一般而言，欲寻找自某关系结构至另一关系结构的同态，属于约束满足问题（constraint satisfaction problem, CSP）。图的特例可作为第一步，帮助理解更复杂的CSP。许多寻找图同构的算法，包括回溯、约束传播（英语：constraint propagation）、局部搜索（英语：Local search (constraint satisfaction)），通用于各种CSP。^[3]

给定图 $G$ 、 $H$ ，问是否有同态 $G\to H$ ，相当于仅得一类约束的CSP实例^[3]：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$ 的同态。

同态的结构

同态的复合仍是同态^[13]，故可知图的 $\to$ 关系具递移性，又显然自反，所以其为图之间的预序。^[27]同态等价意义下，记 $G$ 所属等价类为 $[G]$ ，每个等价类有唯一的核图为其代表。关系 $\to$ 定义该些等价类之间的偏序，即同态等价类构成一个偏序集。^[28]

以 $G<H$ 表示 $G$ 有同态至 $H$ ，但反之则不然。如此定义的序 $<$ 稠密（英语：dense order），即对任意（无向）图 $G,H$ ，若 $G<H$ ，则存在第三幅图 $K$ 使 $G<K<H$ ，除非是平凡反例 $G=K_{0}$ 或 $G=K_{1}$ 。^[29]^[30]例如，任意两幅整数阶完全图（除 $K_{0},K_{1},K_{2}$ 外）之间，必有无穷多幅环状完全图（英语：circular clique），相当于整阶数之间的有理数阶数。^[31]

同态等价类的偏序集是分配格，并 $[G]\lor [H]$ 是互斥并 $[G\sqcup H]$ ，而交 $[G]\land [H]$ 是图张量积（英语：tensor product of graphs） $[G\times H]$ ，其定义不取决于等价类中所选的代表 $G,H$ 。^[32]此格中，并不可约元（英语：join-irreducible）^{[注 5]}正好是连通图，证明方式是留意同态衹会将连通图映到目标的一个连通分支中。^[33]^[34]交不可约元（英语：meet-irreducible）^{[注 5]}正好是积性图（英语：Hedetniemi's conjecture）（multiplicative graphs），此种图 $K$ 的特性是，若乘积 $G\times H$ 有同态至 $H$ ，则 $G$ 或 $H$ 两者之一有同态至 $H$ 。如何识别积性图是赫德米猜想（英语：Hedetniemi's conjecture）^[35]的关键。^[36]^[37]

图与同态还组成范畴：图是物件，而同态是态射。^[38]范畴的始物件是空图 $K_{0}$ ，终物件有一个顶点和一个自环。图张量积（英语：tensor product of graphs）是范畴论积，指数图（英语：Hedetniemi's conjecture）^{[注 6]}是该范畴的指数物件（英语：exponential object）。换言之，自 $G\times H\to K$ 的同态与 $H\to K^{G}$ 的同态自然地一一对应。^[37]^[39]由于对任意图 $G,H$ ，张量积 $G\times H$ 与幂 $H^{G}$ 总有定义，图范畴是笛卡儿闭范畴。同理，同态等价类组成的格实际上是海廷代数：按海廷代数的语言，前述的积称为交运算 $\land$ ，而前述的指数运算称为蕴涵 $\Rightarrow$ 。^[37]^[39]

对于有向图，适用同样的定义。同样有 $\to$ 是有向图同态等价类之间的偏序，其与无向图等价类的偏序 $\to$ 有别，但后者是前者的子序，因为无向图亦可视为有向图，衹是其中每条有向边 $(u,v)$ 皆与其反向 $(v,u)$ 成对出现。换言之，无向图同态的定义，与双向有向图的同态并无区别。有向图的 $\to$ 序仍是分配格和海延代数，交与并的定义亦同上，但分别在于，该序并不稠密。亦有以有向图为物件、同态为态射的范畴，照样笛卡儿闭。^[40]^[39]

不可比图

格勒奇图（英语：Grötzsch graph），与

K_{3}

不可比

同态预序下，许多图不可比较。两幅不可比图（incomparable graphs）之间，并无自任意一幅至另一幅的同态。^[41]欲构造此种图，可考虑图的奇围长，即最短的奇环长度。奇围长可等价地说成最小的奇数 $g$ ，使 $g$ 个顶点的循环图 $C_{g}$ 有同态至 $G$ 。由此定义，若 $G\to H$ ，则 $G$ 的奇围长大于或等于 $H$ 的奇围长。^[42]

另一方面，前节已证若 $G\to H$ ，则 $G$ 的色数小于或等于 $H$ 的色数。所以，若 $G$ 的奇围长及色数皆严格大于 $H$ ，则 $G$ 和 $H$ 不可比较。^[41] 举例，格勒奇图（英语：Grötzsch graph）色数为 $4$ ，且无三角形（围长 $4$ ，奇围长 $5$ ）^[43]，所以与三角形 $K_{3}$ 不可比。

有几类图的奇围长和色数可取任意大，如克内泽尔图（英语：Kneser graph）^[44]与广义梅切尔斯基图（英语：Mycielskian）^[45]。如此一类图，若使其两参数同时递增，排成一列，则有无穷多幅不可比图（同态预序下的反链）。^[46] 同态预序稠密（英语：dense order）等其他性质，亦可利用此类图证明。^[47]此外，可构造同时具大色数和大围长（不仅是奇围长）的图，但较复杂，见围长 (图论) § 围长与图染色。

有向图之中，更易找到不可比图。例如，考虑有向环 ${\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}}}$ 两两不可比。^[48]

计算复杂度

图同态问题是给定一对图 $(G,H)$ ，求自 $G$ 至 $H$ 的图同态。对应的决定性问题问是否存在此种解。一般情况下，即询问的实例 $(G,H)$ 不受额外限制的情况下，此决定性问题为NP完全。^[49]若限制询问的范围，衹限从某类图中选出 $G$ 或 $H$ ，则可得多种不同的问题，其中有些较易求解。限制左边 $G$ 和限制右边 $H$ 相比，适用的方法相去甚远，但两者似乎有一共同特点：难易情况之间似乎有明确的分界，此分界或者已获证，或有论文猜想如此。

至给定图的同态

图同态问题若固定右边的图 $H$ 不变，则称为染 $H$ 色问题。 $H$ 为完全图 $K_{k}$ 时，化成染k色问题，在 $k=0,1,2$ 时，可于多项式时间内求解，但其馀情况则是NP完全。^[50] $k=2$ 的情况相当于问图 $G$ 可否染 $K_{2}$ 色，即是否二部图，此问题可在线性时间内求解。更一般地，衹要 $H$ 是二部图就有同一结论：可染 $H$ 色等价于可染 $K_{2}$ 色，即可染二色，故此种情况同样易判断。可染 $K_{0}$ 色和可染 $K_{1}$ 色分别等价于无顶点和无边，亦易判断。^[51]帕沃尔·黑尔（英语：Pavol Hell）和雅罗斯拉夫·内舍特日尔（英语：Jaroslav Nešetřil）证明，对无向图而言，无其他情况可驯顺：

（黑尔-内舍特日尔定理，1990年）若 $H$ 为二部图，则染 $H$ 色问题属于P，但其馀情况则为NP完全。^[52]^[53]

上述定理又称为无向图同态的“对分定理”（dichotomy theorem），因为将染 $H$ 色问题分成NP完全与P两类，而无居中（英语：NP-intermediate）情况。有向图情况较复杂，此时问题等价于刻画看似更一般的约束满足问题的复杂度（英语：Complexity of constraint satisfaction）^[54]：有向图的染 $H$ 色问题，与允许各种约束条件的CSP相比，同样多姿多彩，而不失一般性。^[55]^[56]严格而言，定义（有限）约束语言（constraint language，或称模板template） $\Gamma$ 为一个有限的取值域，其上配备有限多种关系，然后以 ${\mathsf {CSP}}(\Gamma )$ 表示约束衹能选自 $\Gamma$ 的一类约束满足问题，则有以下定理：

（费德、瓦迪（英语：Moshe Y. Vardi），1998年）对任意约束语言 $\Gamma$ ，必有某幅有向图 $H$ ，使 ${\mathsf {CSP}}(\Gamma )$ 在多项式时间归约意义下等价于染 $H$ 色问题。^[56]

直观理解，定理意味着任何算法技巧或复杂度结论，若适用于一般有向图 $H$ 的染 $H$ 色问题，则可套用至一般CSP。考虑将黑尔-内舍特日尔定理扩展至有向图。由上述定理，该推广等价于有关CSP对分的费德-瓦迪猜想（又称CSP猜想、对分猜想），即断言对任意约束语言 $\Gamma$ ， ${\mathsf {CSP}}(\Gamma )$ 或属NP完全，或属P。^[49]此猜想于2017年由德米特里·祖克（Dmitry Zhuk）与安德烈·布拉托夫（Andrei Bulatov）分别独立证出，故有以下推论：

（布拉托夫2017年；祖克2017年）给定 $H$ 时，有向图的染 $H$ 色问题或属P，或属NP完全。

自给定族的同态

若左输入 $G$ 为给定，则图同态问题有暴力解法，即穷举 $G$ 的各个顶点在 $H$ 中的像，复杂度仅为 ${\mathcal {O}}\left(|V(H)|^{|V(G)|}\right)$ ，已是输入 $H$ 的多项式函数。^[57]换言之，限制 $G$ 的大小时，问题显然属P，但仍可改为研究另一课题：除大小之外，是否其他限制可施加于 $G$ ，使图同态问题可于多项式时间内求解？

研究表明，关键性质是树阔（英语：treewidth），此参数衡量一幅图有多似一棵树。若 $G$ 的树阔至多为 $k$ ，而 $H$ 为任意图，则利用标准的动态规划方法，可于 $|V(H)|^{{\mathcal {O}}(k)}$ 时间内求解图同态问题。实际甚至衹需假设 $G$ 的核的树阔不逾 $k$ ，而无需知道其核为何。^[58]^[59]

该 $|V(H)|^{{\mathcal {O}}(k)}$ 算法中，复杂度的指数可能无法再压低太多：若指数时间假设（英语：exponential time hypothesis）^{[注 7]}（ETH）为真，则不存在时间复杂度为 $|V(H)|^{o(\mathrm {tw} (G)/\log \mathrm {tw} (G))}$ 的算法。即使限制 $G$ 衹能取值为某一族图，衹要该族图的树阔无上界，则仍有同样结论。^[60]同样假设下，几乎没有其他性质使问题可于多项式时间内求解，具体含义如下：

（格罗厄（英语：Martin Grohe））假定ETH，并给定由图组成的可计算族 ${\mathcal {G}}$ 。考虑输入为 $(G,H)$ ，且 $G\in {\mathcal {G}}$ 的图同态问题。此问题属P当且仅当 ${\mathcal {G}}$ 中各图之核的树阔有界。^[59]

或考虑有所取舍，允许复杂度高度依赖 $G$ ，换取复杂度与 $H$ 的关系仅为固定的多项式。与前段类似，若 $G$ 的取值范围中，核的树阔有界，则此目标可以实现，但若 $G$ 的取值范围不满足该条件，则无法达成。^[59]利用带参数复杂度（英语：parameterized complexity）术语，上述成果可覆述为： ${\mathcal {G}}$ 中的同态问题，以 $G$ 的边数为参数，呈现对分现象。若 ${\mathcal {G}}$ 中各图之核的树阔有上界，则该问题为固定参数可驯顺（英语：fixed-parameter tractable），否则为W[1]（英语：Parameterized complexity）完全。

同一命题对其他关系结构亦成立。换言之，其适用于一般的约束满足问题，不过需要限制各项约束涉及的变量数有上界，即关系的元数有上界（以图为例，仅得元数为2的关系）。此时，关键参数为原始约束图（英语：primal constraint graph）^{[注 8]}的树阔。^[60]

参见

图论术语
同态，其他代数结构的同一概念
图重写（英语：Graph rewriting）
中位图（英语：Median graph），可定义成超立方图（英语：hypercube graph）的收缩核
西多连科猜想（英语：Sidorenko's conjecture）

注

^ 使该图可染 $k$ 色的最小 $k$ 值。
^ 取 $0$ 至 $n-1$ 为 $n$ 个顶点，相异两点 $u,v$ 间有连边当且仅当模 $n$ 运算时， $|u-v|$ 大于某定值。
^ 数学流传（英语：Mathematical folklore），谓难以溯源或原创者并无正式投稿出版，但广为研究者熟知的定理。
^ ${\overrightarrow {P_{n}}}$ 的顶点为 $1,2,\ldots ,n$ ，且对每个 $i=1,2,\ldots ,n-1$ 有一条边自 $i$ 至 $i+1$ 。
^ ^5.0 ^5.1 $x$ 为并不可约，意即 $x=a\lor b$ 推出 $x=a$ 或 $x=b$ 。对偶概念为交不可约。
^ 指数图（exponential graph） $H^{G}$ 的顶点是函数 $f:V(G)\to V(H)$ ，两顶点 $f,g:V(G)\to V(H)$ 连边当且仅当对 $G$ 中任意两个相邻顶点 $v,v'$ ，有 $f(v)$ 与 $g(v')$ 在 $H$ 中相邻。
^ 指数时间假设与P ≠ NP类似，皆是未获证的复杂度假设，但前者更强。
^ 约束满足问题中，以变数为顶点，两变数有出现在同一个约束中则连边，可得“原始约束图”。此即以各约束为边的超图的原始图（英语：primal graph）。

参考资料

^ Hell & Nešetřil 2004，第27页.
^ Hell & Nešetřil 2004，第109页.
^ ^3.0 ^3.1 ^3.2 ^3.3 Hell & Nešetřil 2008.
^ ^4.0 ^4.1 引论见诸：Cameron (2006); Hahn & Tardif (1997); Hell & Nešetřil (2004). 由短至长排。
^ Hahn & Tardif 1997，Observation 2.3.
^ Godsil & Royle 2001，第115页.
^ ^7.0 ^7.1 Hell & Nešetřil 2004，第19页.
^ Hell & Nešetřil 2004，Proposition 1.31.
^ Cameron 2006，Proposition 2.3; Hell & Nešetřil 2004，Corollary 1.32.
^ Hell & Nešetřil 2004，第34页.
^ Cameron 2006，第4页，Proposition 2.5.
^ ^12.0 ^12.1 Cameron 2006，第1页; Hell & Nešetřil 2004，Proposition 1.7.
^ ^13.0 ^13.1 Hell & Nešetřil 2004，§1.7.
^ Hell & Nešetřil 2004，Corollary 1.8.
^ Hell & Nešetřil 2004，§6.1; Hahn & Tardif 1997，§4.4.
^ Hell & Nešetřil 2004，§6.2; Hahn & Tardif 1997，§4.5.
^ Hell & Nešetřil 2004，§6.3.
^ Hell & Nešetřil 2004，§6.4.
^ Fiala, J.; Kratochvíl, J., Partial covers of graphs [图之部分覆盖], Discussiones Mathematicae Graph Theory, 2002, 22 (1): 89–99, S2CID 17507393, doi:10.7151/dmgt.1159 （英语）
^ Hell & Nešetřil 2004，第13–14页.
^ Hell & Nešetřil 2004，Proposition 1.20.
^ ^22.0 ^22.1 Cameron 2006，第1页.
^ Hell & Nešetřil 2004，§1.8.
^ Hell & Nešetřil 2004，第30–31页.
^ Hell & Nešetřil 2004，第31–32页.
^ Hell & Nešetřil 2004，第28页，该书称关系结构（relational structures）为“关系系统”（relational systems）。
^ Hell & Nešetřil 2004，§3.1.
^ Hell & Nešetřil 2004，Theorem 3.1.
^ Hell & Nešetřil 2004，Theorem 3.30; Hahn & Tardif 1997，Theorem 2.33.
^ Welzl, E., Color-families are dense [染色族稠密], Theoretical Computer Science（英语：Theoretical Computer Science (journal)）, 1982, 17: 29–41, doi:10.1016/0304-3975(82)90129-3  （英语）
^ Hell & Nešetřil 2004，第192页; Hahn & Tardif 1997，第127页.
^ Hell & Nešetřil 2004，Proposition 3.2，分配律载于Proposition 2.4；又见Hahn & Tardif 1997，Theorem 2.37.
^ Kwuida, Léonard; Lehtonen, Erkko, On the Homomorphism Order of Labeled Posets [论标号偏序集之同态序], Order（英语：Order (journal)）, 2011, 28 (2): 251–265, S2CID 14920600, arXiv:0911.0200  , doi:10.1007/s11083-010-9169-x （英语）
^ Gray 2014，Lemma 3.7.
^ 译名见陈宏宾. 捉住黑暗中的微光，年輕數學家希多夫擊破［赫德米猜想］. UniMath. 2020-02-22 [2021-12-21]. （原始内容存档于2021-12-21）.
^ Tardif, C., Hedetniemi's conjecture, 40 years later [赫德米猜想四十年] (PDF), Graph Theory Notes of New York, 2008, 54: 46–57 [2021-12-21], MR 2445666, （原始内容 (PDF)存档于2021-07-12）（英语） .
^ ^37.0 ^37.1 ^37.2 Dwight, D.; Sauer, N., Lattices arising in categorial investigations of Hedetniemi's conjecture [以范畴论研究赫德米猜想所得的格], Discrete Mathematics（英语：Discrete Mathematics (journal)）, 1996, 152 (1–3): 125–139, doi:10.1016/0012-365X(94)00298-W  （英语）
^ Hell & Nešetřil 2004，第125页.
^ ^39.0 ^39.1 ^39.2 Gray 2014.
^ Brown et al. 2008.
^ ^41.0 ^41.1 Hell & Nešetřil 2004，第7页.
^ Hahn & Tardif 1997，Observation 2.6.
^ Weisstein, Eric W. (编). Grötzsch Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
^ Hahn & Tardif 1997，Proposition 3.14.
^ Gyárfás, A.; Jensen, T.; Stiebitz, M., On Graphs With Strongly Independent Color-Classes [论色类强独立之图], Journal of Graph Theory（英语：Journal of Graph Theory）, 2004, 46 (1): 1–14, doi:10.1002/jgt.10165
^ Hell & Nešetřil 2004，Proposition 3.4.
^ Hell & Nešetřil 2004，第96页.
^ Hell & Nešetřil 2004，第35页.
^ ^49.0 ^49.1 Bodirsky 2007，§1.3.
^ Hell & Nešetřil 2004，§5.1.
^ Hell & Nešetřil 2004，Proposition 5.1.
^ Hell & Nešetřil 2004，§5.2.
^ Hell, Pavol; Nešetřil, Jaroslav. On the complexity of H-coloring [论染H色之复杂度]. Journal of Combinatorial Theory, Series B（英语：Journal of Combinatorial Theory, Series B）. 1990, 48 (1): 92–110. doi:10.1016/0095-8956(90)90132-J  （英语）.
^ Hell & Nešetřil 2004，§5.3.
^ Hell & Nešetřil 2004，Theorem 5.14.
^ ^56.0 ^56.1 Feder, Tomás; Vardi, Moshe Y. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory [单调单子SNP与约束满足之计算结构：藉Datalog与群论研究]. SIAM Journal on Computing（英语：SIAM Journal on Computing）. 1998, 28 (1): 57–104 [2022-02-06]. doi:10.1137/S0097539794266766. （原始内容存档于2022-02-06）（英语）.
^ Cygan, M.; Fomin, F. V.; Golovnev, A.; Kulikov, A. S.; Mihajlin, I.; Pachocki, J.; Socała, A. Tight bounds for graph homomorphism and subgraph isomorphism [图同态与子图同构之紧限界]. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). SIAM（英语：Society for Industrial and Applied Mathematics）: 1643–1649. 2016. Bibcode:2015arXiv150703738F. ISBN 978-1-611974-33-1. arXiv:1507.03738  （英语）.
^ Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics [约束满足、有界树阔、有限变数逻辑]. 8th International Conference on Principles and Practice of Constraint Programming (CP 2002): 310–326. 2002. doi:10.1007/3-540-46135-3_21 （英语）.
^ ^59.0 ^59.1 ^59.2 Grohe, Martin, The complexity of homomorphism and constraint satisfaction problems seen from the other side [同态与约束满足之复杂度，自另一方面观之], Journal of the ACM, 2007, 54 (1): 1–es, S2CID 11797906, doi:10.1145/1206035.1206036 （英语）
^ ^60.0 ^60.1 Marx, Dániel, Can You Beat Treewidth? [可以胜过树阔乎？], Theory of Computing, 2010, 6: 85–112, doi:10.4086/toc.2010.v006a005  （英语）

一般书目、解说

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]. ISBN 0-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（英语：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）（英语）.

[14] 使该图可染 $k$ 色的最小 $k$ 值。

[16] 取 $0$ 至 $n-1$ 为 $n$ 个顶点，相异两点 $u,v$ 间有连边当且仅当模 $n$ 运算时， $|u-v|$ 大于某定值。

[23] 数学流传（英语：Mathematical folklore），谓难以溯源或原创者并无正式投稿出版，但广为研究者熟知的定理。

[24] ${\overrightarrow {P_{n}}}$ 的顶点为 $1,2,\ldots ,n$ ，且对每个 $i=1,2,\ldots ,n-1$ 有一条边自 $i$ 至 $i+1$ 。

[irred-37] 5.0 ^5.1 $x$ 为并不可约，意即 $x=a\lor b$ 推出 $x=a$ 或 $x=b$ 。对偶概念为交不可约。

[44] 指数图（exponential graph） $H^{G}$ 的顶点是函数 $f:V(G)\to V(H)$ ，两顶点 $f,g:V(G)\to V(H)$ 连边当且仅当对 $G$ 中任意两个相邻顶点 $v,v'$ ，有 $f(v)$ 与 $g(v')$ 在 $H$ 中相邻。

[66] 指数时间假设与P ≠ NP类似，皆是未获证的复杂度假设，但前者更强。

[68] 约束满足问题中，以变数为顶点，两变数有出现在同一个约束中则连边，可得“原始约束图”。此即以各约束为边的超图的原始图（英语：primal graph）。

[FOOTNOTEHellNešetřil200427-1] Hell & Nešetřil 2004，第27页.

[FOOTNOTEHellNešetřil2004109-2] Hell & Nešetřil 2004，第109页.

[FOOTNOTEHellNešetřil2008-3] 3.0 ^3.1 ^3.2 ^3.3 Hell & Nešetřil 2008.

[intros-4] 4.0 ^4.1 引论见诸：Cameron (2006); Hahn & Tardif (1997); Hell & Nešetřil (2004). 由短至长排。

[FOOTNOTEHahnTardif1997Observation_2.3-5] Hahn & Tardif 1997，Observation 2.3.

[FOOTNOTEGodsilRoyle2001115-6] Godsil & Royle 2001，第115页.

[FOOTNOTEHellNešetřil200419-7] 7.0 ^7.1 Hell & Nešetřil 2004，第19页.

[FOOTNOTEHellNešetřil2004Proposition_1.31-8] Hell & Nešetřil 2004，Proposition 1.31.

[FOOTNOTECameron2006Proposition_2.3HellNešetřil2004Corollary_1.32-9] Cameron 2006，Proposition 2.3; Hell & Nešetřil 2004，Corollary 1.32.

[FOOTNOTEHellNešetřil200434-10] Hell & Nešetřil 2004，第34页.

[FOOTNOTECameron20064Proposition_2.5-11] Cameron 2006，第4页，Proposition 2.5.

[FOOTNOTECameron20061HellNešetřil2004Proposition_1.7-12] 12.0 ^12.1 Cameron 2006，第1页; Hell & Nešetřil 2004，Proposition 1.7.

[FOOTNOTEHellNešetřil2004§1.7-13] 13.0 ^13.1 Hell & Nešetřil 2004，§1.7.

[FOOTNOTEHellNešetřil2004Corollary_1.8-15] Hell & Nešetřil 2004，Corollary 1.8.

[FOOTNOTEHellNešetřil2004§6.1HahnTardif1997§4.4-17] Hell & Nešetřil 2004，§6.1; Hahn & Tardif 1997，§4.4.

[FOOTNOTEHellNešetřil2004§6.2HahnTardif1997§4.5-18] Hell & Nešetřil 2004，§6.2; Hahn & Tardif 1997，§4.5.

[FOOTNOTEHellNešetřil2004§6.3-19] Hell & Nešetřil 2004，§6.3.

[FOOTNOTEHellNešetřil2004§6.4-20] Hell & Nešetřil 2004，§6.4.

[21] Fiala, J.; Kratochvíl, J., Partial covers of graphs [图之部分覆盖], Discussiones Mathematicae Graph Theory, 2002, 22 (1): 89–99, S2CID 17507393, doi:10.7151/dmgt.1159 （英语）

[FOOTNOTEHellNešetřil200413–14-22] Hell & Nešetřil 2004，第13–14页.

[FOOTNOTEHellNešetřil2004Proposition_1.20-25] Hell & Nešetřil 2004，Proposition 1.20.

[FOOTNOTECameron20061-26] 22.0 ^22.1 Cameron 2006，第1页.

[FOOTNOTEHellNešetřil2004§1.8-27] Hell & Nešetřil 2004，§1.8.

[FOOTNOTEHellNešetřil200430–31-28] Hell & Nešetřil 2004，第30–31页.

[FOOTNOTEHellNešetřil200431–32-29] Hell & Nešetřil 2004，第31–32页.

[HN-csp-30] Hell & Nešetřil 2004，第28页，该书称关系结构（relational structures）为“关系系统”（relational systems）。

[FOOTNOTEHellNešetřil2004§3.1-31] Hell & Nešetřil 2004，§3.1.

[FOOTNOTEHellNešetřil2004Theorem_3.1-32] Hell & Nešetřil 2004，Theorem 3.1.

[FOOTNOTEHellNešetřil2004Theorem_3.30HahnTardif1997Theorem_2.33-33] Hell & Nešetřil 2004，Theorem 3.30; Hahn & Tardif 1997，Theorem 2.33.

[34] Welzl, E., Color-families are dense [染色族稠密], Theoretical Computer Science（英语：Theoretical Computer Science (journal)）, 1982, 17: 29–41, doi:10.1016/0304-3975(82)90129-3  （英语）

[FOOTNOTEHellNešetřil2004192HahnTardif1997127-35] Hell & Nešetřil 2004，第192页; Hahn & Tardif 1997，第127页.

[36] Hell & Nešetřil 2004，Proposition 3.2，分配律载于Proposition 2.4；又见Hahn & Tardif 1997，Theorem 2.37.

[38] Kwuida, Léonard; Lehtonen, Erkko, On the Homomorphism Order of Labeled Posets [论标号偏序集之同态序], Order（英语：Order (journal)）, 2011, 28 (2): 251–265, S2CID 14920600, arXiv:0911.0200  , doi:10.1007/s11083-010-9169-x （英语）

[FOOTNOTEGray2014Lemma_3.7-39] Gray 2014，Lemma 3.7.

[40] 译名见陈宏宾. 捉住黑暗中的微光，年輕數學家希多夫擊破［赫德米猜想］. UniMath. 2020-02-22 [2021-12-21]. （原始内容存档于2021-12-21）.

[41] Tardif, C., Hedetniemi's conjecture, 40 years later [赫德米猜想四十年] (PDF), Graph Theory Notes of New York, 2008, 54: 46–57 [2021-12-21], MR 2445666, （原始内容 (PDF)存档于2021-07-12）（英语） .

[lattices-42] 37.0 ^37.1 ^37.2 Dwight, D.; Sauer, N., Lattices arising in categorial investigations of Hedetniemi's conjecture [以范畴论研究赫德米猜想所得的格], Discrete Mathematics（英语：Discrete Mathematics (journal)）, 1996, 152 (1–3): 125–139, doi:10.1016/0012-365X(94)00298-W  （英语）

[FOOTNOTEHellNešetřil2004125-43] Hell & Nešetřil 2004，第125页.

[FOOTNOTEGray2014-45] 39.0 ^39.1 ^39.2 Gray 2014.

[FOOTNOTEBrownMorrisShrimptonWensley2008-46] Brown et al. 2008.

[FOOTNOTEHellNešetřil20047-47] 41.0 ^41.1 Hell & Nešetřil 2004，第7页.

[FOOTNOTEHahnTardif1997Observation_2.6-48] Hahn & Tardif 1997，Observation 2.6.

[49] Weisstein, Eric W. (编). Grötzsch Graph. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.

[FOOTNOTEHahnTardif1997Proposition_3.14-50] Hahn & Tardif 1997，Proposition 3.14.

[51] Gyárfás, A.; Jensen, T.; Stiebitz, M., On Graphs With Strongly Independent Color-Classes [论色类强独立之图], Journal of Graph Theory（英语：Journal of Graph Theory）, 2004, 46 (1): 1–14, doi:10.1002/jgt.10165

[FOOTNOTEHellNešetřil2004Proposition_3.4-52] Hell & Nešetřil 2004，Proposition 3.4.

[FOOTNOTEHellNešetřil200496-53] Hell & Nešetřil 2004，第96页.

[FOOTNOTEHellNešetřil200435-54] Hell & Nešetřil 2004，第35页.

[FOOTNOTEBodirsky2007§1.3-55] 49.0 ^49.1 Bodirsky 2007，§1.3.

[FOOTNOTEHellNešetřil2004§5.1-56] Hell & Nešetřil 2004，§5.1.

[FOOTNOTEHellNešetřil2004Proposition_5.1-57] Hell & Nešetřil 2004，Proposition 5.1.

[FOOTNOTEHellNešetřil2004§5.2-58] Hell & Nešetřil 2004，§5.2.

[59] Hell, Pavol; Nešetřil, Jaroslav. On the complexity of H-coloring [论染H色之复杂度]. Journal of Combinatorial Theory, Series B（英语：Journal of Combinatorial Theory, Series B）. 1990, 48 (1): 92–110. doi:10.1016/0095-8956(90)90132-J  （英语）.

[FOOTNOTEHellNešetřil2004§5.3-60] Hell & Nešetřil 2004，§5.3.

[FOOTNOTEHellNešetřil2004Theorem_5.14-61] Hell & Nešetřil 2004，Theorem 5.14.

[FederVardi-62] 56.0 ^56.1 Feder, Tomás; Vardi, Moshe Y. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory [单调单子SNP与约束满足之计算结构：藉Datalog与群论研究]. SIAM Journal on Computing（英语：SIAM Journal on Computing）. 1998, 28 (1): 57–104 [2022-02-06]. doi:10.1137/S0097539794266766. （原始内容存档于2022-02-06）（英语）.

[63] Cygan, M.; Fomin, F. V.; Golovnev, A.; Kulikov, A. S.; Mihajlin, I.; Pachocki, J.; Socała, A. Tight bounds for graph homomorphism and subgraph isomorphism [图同态与子图同构之紧限界]. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). SIAM（英语：Society for Industrial and Applied Mathematics）: 1643–1649. 2016. Bibcode:2015arXiv150703738F. ISBN 978-1-611974-33-1. arXiv:1507.03738  （英语）.

[64] Dalmau, Víctor; Kolaitis, Phokion G.; Vardi, Moshe Y. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics [约束满足、有界树阔、有限变数逻辑]. 8th International Conference on Principles and Practice of Constraint Programming (CP 2002): 310–326. 2002. doi:10.1007/3-540-46135-3_21 （英语）.

[Grohe-65] 59.0 ^59.1 ^59.2 Grohe, Martin, The complexity of homomorphism and constraint satisfaction problems seen from the other side [同态与约束满足之复杂度，自另一方面观之], Journal of the ACM, 2007, 54 (1): 1–es, S2CID 11797906, doi:10.1145/1206035.1206036 （英语）

[marx-67] 60.0 ^60.1 Marx, Dániel, Can You Beat Treewidth? [可以胜过树阔乎？], Theory of Computing, 2010, 6: 85–112, doi:10.4086/toc.2010.v006a005  （英语）

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[注 1]

[14]

[注 2]

[15]

[16]

[17]

[18]

[19]

[20]

[注 3]

[注 4]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[注 5]

[33]

[34]

[35]

[36]

[37]

[38]

[注 6]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[注 7]

[60]

[注 8]