一般に，準同型写像を2つ合成すると準同型になる． グラフの準同型の場合も例外ではなく，準同型2つを合成して準同型を得ることができる． つまり，f:G1→G2とg:G2→G3の2つの準同型が存在したら，gｏf(u)=g(f(u))と定義することにより，gｏf:G1→G3という写像が得られるが，このgｏfは必ず準同型になる． (∵uvが辺 → f(u)f(v)が辺 → g(f(u))g(f(v))が辺．)
この性質を利用するといろいろなことが簡単に言えるようになる．
例えば，次の定理がある．
|
定理(Lovász 1978)： クネーザーグラフKn:kの彩色数はn-2k+2である． |
この定理の証明は実は難しく，位相幾何学の知識などがないと証明を追うことが出来ない(注：Matousekが組合せ的証明を与えているが，これも難しい)のであるが，とりあえずこの事実は知っていることとしよう．
すると，2章で見たように，これは，Kn:k→Kn-2k+2という準同型が存在することを意味する．
一方，もし，あるグラフGのk重n-彩色可能であるとすると，これは，3章で見たように， G→Kn:kという準同型が存在することを意味する． ここで，この準同型と先の準同型を合成すると，自動的にG→Kn-2k+2という準同型が存在することまで分かる．そして，これはGがn-2k+2色で彩色できることと等価である． つまり，グラフGがk重n-彩色可能であれば，Gは(n-2k+2)-彩色可能である，ということになる． したがって，次が言えることになる．
|
定理： χ(G) ≦ χk(G)-2k+2． |
分数彩色χfに関しては，χf=limk→∞χk(G)/kであるが，これはinfkχk(G)/kに等しく，また，この値が必ずある有限のkで(有理数として)実現されるということが知られている．これを使うと，次のようなことも分かる．
|
定理： χf(G)=a/bのとき，χ(G) ≦ a-2b+2． |
また，次のように，「準同型が存在しない」ということをいうのにもこの準同型の合成の議論が使える．
まず，サイズkの有向パスDPkとサイズkのトーナメントグラフTkを考えてみる．ここで，DPkからTkへの準同型が存在しないことはすぐに分かる．
(∵ DPkはk+1頂点あり，Tkはk頂点しかないため，もし準同型fがあるとするとDPkのある2つの頂点uiとujがTkの同じ頂点f(ui)=f(ujに写されなければならないが，そうすると，Tkにおいてf(ui)→f(ui+1)→…→f(uSUB>j)という有向サイクル(j=i+1のときはループ)が存在することになってしまう(Tkは有向サイクルもループも持たない)．)
すると，準同型の合成の議論を使うと次のことが言えるはずである．
さて，ここで，この逆について考えてみよう．
有向グラフGに対して，DPkからGへの準同型が存在しないとする．
このとき，Gは有向サイクルを持たない(非巡回的である)はずである．なぜなら，Gにもし有向サイクルがあれば，DPkをこのサイクル上に写す準同型が存在するはずだからである．
さらに，Gにおいて，極大な有向パスはすべて長さがk-1以下である．(長さk以上のパスがあったら，そこにDPkを準同型で写せてしまう．)
これらに着目して，次のようにGの各頂点に番号を付ける．
|
定理： 有向グラフに対して，次の2つのうちのいずれかちょうど一方が成立する．
|
この定理からはもう少し面白いことが言える．
|
定理： (無向)グラフGがk-彩色可能であることと，Gに長さkの有向パスDPkを含まないような非巡回的な向き付けが存在することは等価である． |
(証明)
もし，Gがk-彩色可能であれば，1〜kの色で彩色をし，小さい色から大きい色の方向に各辺を向き付ければ，長さkの有向パスを含まない非巡回的向き付けが得られる．
一方，Gがk-彩色可能でないとすると，Gからサイズkの完全グラフKkへの準同型は存在しない．したがって，Gをどのように向き付けても，得られる有向グラフからサイズkのトーナメントグラフTnへの準同型は存在しない． 上の定理を使うと，これは，Gをどのように非巡回的に向き付けても，得られる有向グラフに長さkの有向パスDPkからの準同型が存在することになる． ここで，非巡回的な向き付けなので，この準同型によるDPkの像は長さkの有向パスになる． すなわち，GにはDPkを含まないような非巡回的な向き付けは存在しない． □