Es seien ${\displaystyle {}G=(V,E)}$ und ${\displaystyle {}H=(W,F)}$ Graphen. Eine Abbildung ${\displaystyle {}\varphi \colon V\rightarrow W}$ mit der Eigenschaft, dass aus ${\displaystyle {}vv'\in E}$ entweder ${\displaystyle {}\varphi (v)=\varphi (v')}$ oder aber ${\displaystyle {}\varphi (v)\varphi (v')\in F}$ folgt, heißt schwacher Graphhomomorphismus.