具体例での説明2
図1の Grötzsch のグラフ で試してみます。(Grötzsch は グレッチュ と読むようです)図1 のように 4色で彩色できますが、3色では彩色できない臨界グラフです。11個の頂点と20個の辺で構成され、3点の完全グラフを含まず、かつ平面的なグラフではありません。
頂点0 に隣接する頂点の集合を H とします( H = {1, 2, 3, 4, 5} )。頂点0 と 頂点0 の辺を取り除いたのが図2です。
着色の条件X, Y を定義します。
- 条件X:全体を 3色以内で着色する。
- 条件Y:全体を 3色以内で着色するが、集合H の頂点は 2色以内とする。
具体例での説明 と同じ方法で計算します。
K4∧R は 9,842項になり、そのうち k∧K4∧R は 3,767項です。 (¬k)∧K4∧R は 6,075項です。
射影をとって重複する項を取り除くと Σ(k∧K4∧R) は 2,547項に、Σ((¬k)∧K4∧R) は 3,676項になります。
Σ(k∧K4∧R) に含まれていない Σ((¬k)∧K4∧R) の項は 2,571項です。その中で1の立ち方が極大となっているものが、420項あります。その一部を表にしました。'_' はグラフに含まれていない辺です。
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 12 | 123 | 1234 | 12345 | 123456 | 1234567 | 12345678 | 123456789 |
_ | __ | ___ | ____ | _0__0 | 0_0__0 | _1_0__1 | __1_1__0 | 1__1_1__0 |
_ | __ | ___ | ____ | _0__0 | 0_0__0 | _1_1__1 | __1_1__0 | 1__0_1__0 |
_ | __ | ___ | ____ | _0__0 | 0_1__0 | _0_0__1 | __1_1__1 | 1__1_1__0 |
_ | __ | ___ | ____ | _0__0 | 0_1__0 | _0_1__1 | __1_1__1 | 1__0_1__0 |
_ | __ | ___ | ____ | _0__0 | 0_1__0 | _1_0__0 | __0_1__1 | 1__1_1__0 |
_ | __ | ___ | ____ | _0__0 | 0_1__0 | _1_0__0 | __1_1__0 | 1__1_1__0 |
_ | __ | ___ | ____ | _0__0 | 0_1__0 | _1_0__1 | __0_1__0 | 1__1_1__0 |
_ | __ | ___ | ____ | _0__0 | 0_1__0 | _1_0__1 | __1_0__1 | 1__1_1__0 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _0_1__0 | __1_0__0 | 0__0_1__0 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _0_1__0 | __1_0__0 | 0__1_0__0 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _0_1__0 | __1_0__0 | 1__0_0__1 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _1_0__0 | __0_0__0 | 0__1_0__1 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _1_0__0 | __0_1__1 | 0__1_0__0 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _1_0__0 | __0_1__1 | 1__0_0__0 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _1_0__0 | __1_0__0 | 0__1_0__0 |
_ | __ | ___ | ____ | _1__1 | 1_1__0 | _1_0__0 | __1_0__0 | 1__0_0__1 |
集合H の中に3点の完全グラフをつくる辺の縮約が 420通りあることになります。表の1番上と下の縮約を図にしました。点線の辺が縮約する辺(負の辺)です。
なお、図1の Grötzsch のグラフは6点の完全グラフに縮約する方法が2つあります。図5と6がそれです。両方とも点対称で、互いに裏返しの関係にあります。
420通りある集合H の中に3点の完全グラフをつくる辺の縮約ですが、5次2面体群D5 の作用で重なるものを1つにまとめ、図にしてみました。44通りになりました。そのうち 線対称になるのは 26, 27, 30, 32 の4つです。対称になっているほうが、きれいに収まってる感じがしないでもありません。