Colorability Problems of Graphs

グラフに関する問題として, 最も良く知られているのは4色問題だろう。既に証明されたので, 4色定理と言うべきだろうが。

• four color problem or four color theorem

Wikipedia など, 様々なところに解説があるが, Schwartz [Sch25] は West の本 [Wes96] を参照している。

この Quanta の記事 に簡単な歴史が書いてあるが, Francis Guthrie という数学者が1854年に考え, やはり数学者であった兄を通してその指導教員だった De Morgan に伝わったことで, 一般に知られるようになったようである。

よく知られているように Appell と Haken [AH76] により 1976年 に 計算機を用いて解決された。 その後単純化された証明が, Robertson, Sanders, Seymour, Thomas [Rob+97] により得られ, 「定理」として認知されるようになったようである。

それより高速な algorithm による証明が Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen, Thorup [Ino+] により発見されている。 上記の Quanta の記事は, この新しい証明に関するものである。

Schwartz [Sch25; Sch26] は連分数との関連について述べている。 Bowlin と Brin [BB13] は, associahedron や Richard Thompson の群 \(V\) を使っている。

この MathOverflow の質問で, Kalai が4色定理の一般化や変種について聞いている。 様々な回答があるが, その中で最も評価が高いのは Hadwiger’s conjecture である。

• Hadwiger’s conjecture

グラフの彩色に関しては, 様々な グラフの不変量が定義される。 基本的なのは彩色数 (chromatic number) であるが, 他にも chromatic polynomial など, 色々ある。

• グラフの色付けに関する不変量

もちろん hypergraph や quiver など, グラフの一般化や変種に対しても, 彩色問題は考えられている。

References

[AH76]

K. Appel and W. Haken. “A proof of the four color theorem”. In: Discrete Math. 16.2 (1976), pp. 179–180. url: https://doi.org/10.1016/0012-365X(76)90147-3.

[BB13]

Garry Bowlin and Matthew G. Brin. “Coloring planar graphs via colored paths in the associahedra”. In: Internat. J. Algebra Comput. 23.6 (2013), pp. 1337–1418. arXiv: 1301.3984. url: https://doi.org/10.1142/S0218196713500276.

[Ino+]

Yuta Inoue et al. The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring. arXiv: 2603.24880.

[Rob+97]

Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. “The four-colour theorem”. In: J. Combin. Theory Ser. B 70.1 (1997), pp. 2–44. url: https://doi.org/10.1006/jctb.1997.1750.

[Sch25]

Richard Evan Schwartz. “Continued fractions and the four color theorem”. In: J. Exp. Math. 1.1 (2025), pp. 149–168. arXiv: 2208.05254.

[Sch26]

Richard Evan Schwartz. “Continued fractions and the four color theorem: erratum”. In: J. Exp. Math. 2.1 (2026), pp. 205–207.

[Wes96]

Douglas B. West. Introduction to graph theory. Prentice Hall, Inc., Upper Saddle River, NJ, 1996, pp. xvi+512. isbn: 0-13-227828-6.