Colorability Problems of Graphs

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

• four color problem or four color theorem

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

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

• Hadwiger’s conjecture

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

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

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

References

[Sch]

Richard Evan Schwartz. Continued Fractions and the 4-Color Theorem. arXiv: 2208.05254.

[Wes96]

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