少なくとも4つの色を必要とする3クリークのないグラフ

Question

次のプロパティを持つグラフの例を挙げてください。

グラフには、サブグラフとして三角形（つまり、3つの頂点のクリーク）が含まれていないことに注意してください。 グラフは、我々は最終試験を持っている1.Tomorrow

[。あなたは、このようなグラフが可能ではないと思われる場合は、その文を証明する] を着色適切な頂点のために、少なくとも4色を必要とし、この質問は上かもしれません試験用紙。 2.このようなグラフを描くことは不可能だと思います。しかし、どのように証明する？ありがとうございます。

Answer 1

ウェブ検索はhttps://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph

Grötzschグラフは、シーケンス内の前のグラフの各Mycielskianは、空グラフから出発三角形フリーグラフの無限配列のメンバーで見出します。グラフのこのシーケンスは、任意に大きな色数を持つ三角形のないグラフが存在することを示すために、Mycielski（1955）によって使用された。したがって、Grötzschグラフは、MycielskiグラフまたはMycielski-Grötzschグラフと呼ばれることもあります。このシーケンスの後のグラフとは異なり、Grötzschグラフは、その有彩色数を持つ最小の三角形グラフです（Chvátal1974）。