Проблема Нельсона — Ердеша — Гадвігера
Проблема Нелсона — Ердеша — Гадвігера — фундаментальна проблема комбінаторної геометрії, спочатку поставлена як задача про розфарбування або хроматичне число евклідового простору. Надалі задача була узагальнена на довільний метричний простір. Цю проблему можна поставити і як завдання теорії графів. Проблема пов'язана також із іншим класичним завданням комбінаторної геометрії — гіпотезою Борсука, спростованою в загальному випадку 1993 року. Попри зусилля низки великих математиків, станом на 2014 р. проблема Нельсона — Ердеша — Гадвігера далека від вирішення.
Див. також
- Гіпотеза Борсука
- Проблема чотирьох фарб
- Теорема де Брейна — Ердеша (теорія графів)
Посилання
- de Bruijn, N. G.; Erdős, P. (1951). A colour problem for infinite graphs and a problem in the theory of relations. Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373..
- Chilakamarri, K. B. (1993). The unit-distance graph problem: a brief survey and some new results. Bull Inst. Combin. Appl. 8: 39–60..
- Chilakamarri, Kiran B.; Mahoney, Carolyn R. (1996). Unit-distance graphs, graphs on the integer lattice and a Ramsey type result. Aequationes Mathematicae 51 (1-2): 48–67. MR 1372782. doi:10.1007/BF01831139..
- Coulson, D. (2004). On the chromatic number of plane tilings. J. Austral. Math. Soc. 77 (2): 191–196. doi:10.1017/S1446788700013574..
- Coulson, D. (2002). A 15-colouring of 3-space omitting distance one. Discrete Math. 256: 83–90. doi:10.1016/S0012-365X(01)00183-2..
- Croft, Hallard T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. Springer-Verlag., Problem G10.
- Gardner, Martin (1960). Mathematical Games. Scientific American. 203/4: 180..
- Hadwiger, Hugo (1945). Überdeckung des euklidischen Raumes durch kongruente Mengen. Portugal. Math. 4: 238–242..
- Hadwiger, Hugo (1961). Ungelöste Probleme No. 40. Elem. Math. 16: 103–104..
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization. с. 150–152..
- Radoičić, Radoš; Tóth, Géza (2003). Note on the chromatic number of the space. Discrete and Computational Geometry: The Goodman–Pollack Festschrift. Algorithms and Combinatorics 25. Berlin: Springer. с. 695–698. MR 2038498. doi:10.1007/978-3-642-55566-4_32..
- Shelah, Saharon; Soifer, Alexander (2003). Axiom of choice and chromatic number of the plane. Journal of Combinatorial Theory, Series A 103 (2): 387–391. doi:10.1016/S0097-3165(03)00102-X. Архів оригіналу за 14 червня 2011..
- Soifer, Alexander (2008). The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. New York: Springer. ISBN 978-0-387-74640-1.,
- Woodall, D. R. (1973). Distances realized by sets covering the plane. Journal of Combinatorial Theory. Series A 14: 187–200. MR 0310770. doi:10.1016/0097-3165(73)90020-4.
Джерела
- O'Rourke, Joseph. Problem 57: Chromatic Number of the Plane. The Open Problems Project. Архів оригіналу за 30 серпня 2006.
- Mohar, Bojan (2001). The chromatic number of the Unit Distance Graph.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.