图同态

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

关于两幅图如何算是“完全一样”，请见“图同构”。

关于允许将边映成路径的映射，请见“图同胚”。

由花形蛇鲨图（英语：flower snark）J₅射向环图C₅的同态，亦是到J₅中央五个顶点所成子图的收缩，所以J₅与其核（英语：core (graph theory)）C₅“同态等价”。

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

定义

本条目中，除非另有声明，否则“图”皆为有限无向图，允许自环，但无重边（两点间连多于一条边）。自${\displaystyle G=(V(G),E(G))}$至另一图${\displaystyle H=(V(H),E(H))}$的图同态^[4]${\displaystyle f}$，记作

${\displaystyle f:G\to H,}$

是顶点集${\displaystyle V(G)}$至${\displaystyle V(H)}$的函数，其将${\displaystyle G}$每条边的两端分别映至${\displaystyle H}$某边的两端。以符号表示：对${\displaystyle V(G)}$中每对顶点${\displaystyle u,v}$，若${\displaystyle \{u,v\}\in E(G)}$，则${\displaystyle \{f(u),f(v)\}\in E(H)}$。若存在${\displaystyle G}$至${\displaystyle H}$的同态，则称${\displaystyle G}$同态于（homomorphic to）${\displaystyle H}$，或可染${\displaystyle H}$色（${\displaystyle H}$-colourable），常简记为：

${\displaystyle G\to H.}$

上述定义可引伸至有向图，此时，${\displaystyle f:G\to H}$为同态的条件是，${\displaystyle G}$中每条有向边${\displaystyle (u,v)}$的像${\displaystyle (f(u),f(v))}$，仍是${\displaystyle H}$的有向边。

自${\displaystyle G}$至${\displaystyle H}$有单同态（将不同顶点映至不同顶点），当且仅当${\displaystyle G}$为${\displaystyle H}$的子图。若同态${\displaystyle f:G\to H}$为双射（两图顶点集的一一对应），且其逆${\displaystyle f^{-1}}$亦是图同态，则${\displaystyle f}$为图同构。^[5]

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

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

核与回缩

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

主条目：核图（英语：Core (graph theory)）

若两幅图${\displaystyle G}$和${\displaystyle H}$有同态${\displaystyle G\to H}$及${\displaystyle H\to G}$，则称两者同态等价（homomorphically equivalent）。^[4]该些映射不必单，也不必满。例如，完全二部图${\displaystyle K_{2,2}}$与${\displaystyle K_{3,3}}$同态等价，因为可将${\displaystyle K_{2,2}}$左部两个顶点映到${\displaystyle K_{3,3}}$左部同一个顶点，其右部的两个顶点映到${\displaystyle K_{3,3}}$右部一个顶点，同样有${\displaystyle K_{3,3}\to K_{2,2}}$的同态。

收缩映射（retraction）是自图${\displaystyle G}$至其子图${\displaystyle H}$的同态${\displaystyle r}$，且对${\displaystyle H}$中每个顶点${\displaystyle v}$有${\displaystyle r(v)=v}$。若有此种映射，则${\displaystyle H}$称为${\displaystyle G}$的收缩核（retract）。^[7]

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

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

与染色的关联

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

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

变式

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

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

无长路径的定向

主条目：高洛伊-哈塞-罗伊-维塔韦尔定理（英语：Gallai–Hasse–Roy–Vitaver theorem）

图同态与图定向（英语：Orientation (graph theory)）也有关。无向图${\displaystyle G}$的定向是赋予每边一个方向（二选一），所得的有向图。同一幅无向图可以有多种不同的定向。举例，完全图${\displaystyle K_{k}}$可定向成“递移循环赛图（英语：Tournament (graph theory)）”${\displaystyle {\overrightarrow {T_{k}}}}$，其顶点为${\displaystyle 1,2,\ldots ,k}$，对所有${\displaystyle i<j}$有（有向）边自${\displaystyle i}$指向${\displaystyle j}$。给定${\displaystyle G}$的定向与${\displaystyle H}$的定向之间的同态，忘掉定向即得本来无向图之间的同态。另一方面，给定无向图同态${\displaystyle G\to H}$，${\displaystyle H}$任何定向${\displaystyle {\overrightarrow {H}}}$可以拉回到${\displaystyle G}$的定向${\displaystyle {\overrightarrow {G}}}$，使原同态亦是${\displaystyle {\overrightarrow {G}}\to {\overrightarrow {H}}}$的有向图同态。综上，无向图${\displaystyle G}$可染${\displaystyle k}$色（即有同态至${\displaystyle K_{k}}$），当且仅当${\displaystyle G}$有某定向，具有至${\displaystyle {\overrightarrow {T_{k}}}}$的同态。^[20]

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

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

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

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

与约束满足问题的关联

范例

图${\displaystyle H}$，表示一周中不相邻的日子，同构于环${\displaystyle C_{7}}$的补图，亦同构于环状团（英语：circular clique）${\displaystyle K_{7/2}}$

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

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

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

抽象观点

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

给定图${\displaystyle G}$、${\displaystyle H}$，问是否有同态${\displaystyle G\to H}$，相当于仅得一类约束的CSP实例^[3]：CSP的“变量”是${\displaystyle G}$的顶点，每个变量的“域”（可取值的范围）是${\displaystyle H}$的顶点集。“赋值”是一个函数，将逐个变量映至域的元素，即函数${\displaystyle f:V(G)\to V(H)}$。${\displaystyle G}$的每条边（或有向边）${\displaystyle (u,v)}$对应一个“约束”${\displaystyle ((u,v),E(H))}$，限制赋值函数将边${\displaystyle (u,v)}$映至关系${\displaystyle E(H)}$中，即映至${\displaystyle H}$的某边。CSP的“解”是满足全体约束的赋值，故前述CSP的解正是自${\displaystyle G}$至${\displaystyle H}$的同态。

同态的结构

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

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

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

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

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

不可比图

格勒奇图（英语：Grötzsch graph），与${\displaystyle K_{3}}$不可比

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

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

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

有向图之中，更易找到不可比图。例如，考虑有向环${\displaystyle {\overrightarrow {C_{n}}}}$，顶点为${\displaystyle 1,2,\ldots ,n}$，有向边自${\displaystyle i}$至${\displaystyle i+1}$（对${\displaystyle i=1,2,\ldots ,n-1}$各一），及自${\displaystyle n}$至${\displaystyle 1}$。对于${\displaystyle n,k\geq 3}$，${\displaystyle {\overrightarrow {C_{n}}}}$至${\displaystyle {\overrightarrow {C_{k}}}}$有同态当且仅当${\displaystyle n}$为${\displaystyle k}$的倍数。所以，当${\displaystyle p}$取质数值时，${\displaystyle {\overrightarrow {C_{p}}}}$两两不可比。^[48]

计算复杂度

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

至给定图的同态

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

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

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

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

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

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

自给定族的同态

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

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

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

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

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

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

参见

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