グラフ準同型のはなし
- グラフの準同型って何？
- 完全グラフへの準同型：グラフの彩色
- クネーザーグラフへの準同型：グラフの分数彩色
- トーナメントグラフへの準同型：非巡回性
- 有向パスへの準同型：balanced graph
- 準同型の合成
- 準同型が存在しない条件
- 準同型同値とcore
グラフ準同型に関する入門者用の紹介記事です。
参考文献としては、
- P. Hell and J. Nesetril, 「Graphs and Homomorphisms」(Oxford University Press) 2004.
- C. Godsil and G. Royle, 「Algebraic Graph Theory」(Springer-Verlag) 2001.
などがあります。他に，
- E.R.Sheinerman & D.H.Ullman, 「Fractional Graph Theory」(John Wiley & Sons) 1997.
も参考にしています．このページで紹介している定理やいろいろな事実はこれらの文献から採ってきています．
ここに記載した内容はごく入門程度のことだけなので，
グラフの準同型に興味を持ってもっと深く勉強してみたいという方は、
上の本やそれに類する文献で勉強してみて下さい。
written by 八森正泰