图同态

图同态是保持边的顶点映射。它允许把原图中不相邻的多个顶点映到目标图的同一个顶点，因此比图同构允许的映射更广。图着色可以写成一种特殊的图同态。

定义

设 $G=(V_G,E_G)$、$H=(V_H,E_H)$ 是简单无向图。若映射 $f:V_G\to V_H$ 满足 $$uv\in E_G⟹f(u)f(v)\in E_H,$$ 则称 $f$ 为从 $G$ 到 $H$ 的图同态。定义只要求边的像仍是边；原图中没有边的两个顶点，其像可以相邻。映射也不要求满射或单射。

一个四顶点例子

取四顶点路径 $1-2-3-4$ 为 $G$，把目标图 $H$ 取成两个顶点 $a,b$ 之间有一条边的 $K_2$。令 $$f(1)=a,f(2)=b,f(3)=a,f(4)=b.$$ 原图的三条边 $12,23,34$ 分别映为 $ab,ba,ab$；无向图中 $ab=ba$，它们都是目标图的边，所以该映射是同态。$1$ 和 $3$ 都映到 $a$，说明同态不必是单射。

相邻顶点映到目标图的不同端点；原图中不相邻的顶点可以合并。

同态与着色

对 $k\ge 1$，目标图 $K_k$ 的不同顶点两两相邻，且没有环。将目标顶点看作 $k$ 种颜色，则 存在图同态 $G\to K_k$，当且仅当 $G$ 可以用至多 $k$ 种颜色合法着色。 证明。 若存在同态，就用 $f(v)$ 给顶点 $v$ 着色。相邻顶点的像必须是 $K_k$ 的一条边，而 $K_k$ 没有环，所以两端颜色不同。反之，合法着色中的每条边两端颜色不同，对应的目标顶点在 $K_k$ 中相邻，因而着色映射是同态。

上面的路径交替使用两种颜色，因而映到 $K_2$。三角形不能映到 $K_2$：设第一个顶点映到 $a$，其两个邻居都必须映到 $b$，但它们彼此相邻，$b$ 上又没有环。一般地，能够映到 $K_2$ 的图恰是二部图。

与同构的区别

图同构要求双射，且边与非边都得到保持；图同态只保证边映为边。即使一个同态恰好是双射，也不能在不检查目标图的其他边时就断言它是同构。例如将三个孤立顶点双射到三角形的三个顶点，源图没有边，保持边的条件自动成立，但目标图有三条边，显然不同构。