Проблема Нельсона — Ердеша — Гадвігера

Проблема Нелсона — Ердеша — Гадвігера — фундаментальна проблема комбінаторної геометрії, спочатку поставлена як задача про розфарбування або хроматичне число евклідового простору. Надалі задача була узагальнена на довільний метричний простір. Цю проблему можна поставити і як завдання теорії графів. Проблема пов'язана також із іншим класичним завданням комбінаторної геометрії — гіпотезою Борсука, спростованою в загальному випадку 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, doi:10.1007/BF01831139, MR 1372782.
• 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 (PDF), Algorithms and Combinatorics, т. 25, Berlin: Springer, с. 695—698, doi:10.1007/978-3-642-55566-4_32, MR 2038498.
• Shelah, Saharon; Soifer, Alexander (2003), Axiom of choice and chromatic number of the plane (PDF), Journal of Combinatorial Theory, Series A, 103 (2): 387—391, doi:10.1016/S0097-3165(03)00102-X, архів оригіналу (PDF) за 14 червня 2011 {{citation}}: Cite має пустий невідомий параметр: |df= (довідка).
• 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, doi:10.1016/0097-3165(73)90020-4, MR 0310770

Джерела

• O'Rourke, Joseph. Problem 57: Chromatic Number of the Plane. The Open Problems Project. Архів оригіналу за 30 серпня 2006. {{cite web}}: Cite має пустий невідомий параметр: |df= (довідка)
• Mohar, Bojan (2001). The chromatic number of the Unit Distance Graph.