在圖論的數學領域，圖的同態性是兩個圖之間尊重其結構的映射。更具體地說，它是兩個圖的頂點集之間的一個函數，將相鄰的頂點映射到相鄰的頂點。同態性概括了圖著色的各種概念，并允許表達一類重要的約束滿足問題，如某些調度或頻率分配問題。同態可以組成的事實導致了豐富的代數結構：圖上的前序、分布格和類別（一個用于無向圖，一個用于有向圖）。在給定的圖之間尋找同態的計算復雜性一般來說是令人望而卻步的，但有很多已知的特殊情況可在多項式時間內解決。可解決和不可解決的情況之間的界限一直是一個活躍的研究領域。

在本文中，除非另有說明，圖是有限的無向圖，允許有循環，但不允許有多條邊（平行邊）。圖同構f從圖G=（V（G），E（G））到圖H=（V（H），E（H）），寫作f:G→H形式上，{u,v}∈E(G)意味著{f(u),f(v)}∈E(H)，適用于V(G)中的所有頂點對u,v。如果存在任何從G到H的同態性，那么G被稱為與H同態或H-可著色。這通常被表示為只是。G→H。上述定義可以擴展到有向圖。那么，對于同構f:G→H，只要(u,v)是G的一個弧，(f(u),f(v))就是H的一個弧（有向邊）。當且僅當G是H的一個子圖時，存在一個從G到H的注入性同構（即一個從不將不同的頂點映射到一個頂點的同構）。如果同構f:G→H是一個雙射（G和H的頂點之間的一對一對應），其反函數也是一個圖同構，那么f就是一個圖同構。覆蓋圖是一種特殊的同態，它反映了拓撲學中覆蓋圖的定義和許多特性。它們被定義為射影同態（即對每個頂點的東西映射），同時也是局部雙射，即對每個頂點的鄰域的雙射。一個例子是雙位數雙覆蓋，由圖形成，將每個頂點v分成v0和v1，用邊u0，v1和v0，u1替換每個邊u，v。覆蓋中的v0和v1映射到原圖中的v的函數是一個同態性和覆蓋圖。圖的同態性是一個不同的概念，與同態性沒有直接關系。粗略地說，它需要注入性，但允許將邊映射到路徑上（而不僅僅是映射到邊上）。圖小數是一個更為寬松的概念。

如果G→H和H→G，那么兩個圖G和H是同態等價的，這些映射不一定是射影的，也不一定是注入的。例如，完整的二方圖K2,2和K3,3是同態等價的：每個映射可以定義為取域圖的左半部（或右半部），并映射到圖像圖的左半部（或右半部）中的一個頂點。縮減是指從圖G到G的子圖H的同態性r，使得對于H的每個頂點v來說，r(v)=v，在這種情況下，子圖H稱為G的縮減。核心圖是一個與任何適當子圖沒有同構關系的圖。等價地，核心可以被定義為不縮減到任何適當子圖的圖。每個圖G都同態地等價于一個xxx的核心（直到同態），稱為G的核心。

然而，同樣的定義適用于有向圖，有向圖也等價于一個xxx的核心。每個圖和每個有向圖都包含其作為縮減和作為誘導子圖的核心。例如，所有完整圖Kn和所有奇數周期（奇數長度的周期圖）都是核心。每個包含三角形的3色圖G（即有完整圖K3作為子圖）都與K3同構。這是因為，一方面，G的3色與G→K3的同構是一樣的，如下文所解釋。另一方面，G的每一個子圖都有一個進入G的同態性，這意味著K3→G，這也意味著K3是任何此類圖G的核心。

對于某個整數k，k著色是指對圖G的每個頂點分配k種顏色中的一種，從而使每條邊的端點得到不同顏色。G的k-著色正好對應于從G到完整圖Kk的同態性。事實上，Kk的頂點對應于k種顏色，當且僅當兩種顏色不同時，它們作為Kk的頂點是相鄰的。因此，當且僅當一個函數將G的相鄰頂點映射到Kk時，它定義了一個與Kk的同構。