Четырёх красок задача

задача, заключающаяся в доказательстве (или опровержении) следующего предложения: четырёх различных красок достаточно для того, чтобы раскрасить любую карту так, чтобы никакие две области, имеющие общий участок границы, не были окрашены в один и тот же цвет. Это предложение подтверждается во всех известных частных случаях (сообщение о его доказательстве было опубликовано лишь в 1976).

В качестве математической задачи оно было сформулировано впервые в середине 19 в. и получило широкую известность благодаря лекциям английского математика О. де Моргана. Чтобы поставить задачу с полной строгостью, надо потребовать, чтобы рассматриваемые области были ограничены простыми замкнутыми контурами (замкнутыми жордановыми кривыми). Без труда можно доказать, что пяти красок всегда достаточно для раскраски такого рода «карты». Если же соответствующую задачу формулировать для пространства, то здесь никакое число «красок» не окажется достаточным.

Лит.: Appel К., Haken W., «Bulletin of the American Mathematical Society», 1976, v. 82, № 5, p. 711—12.

можно ли области любой плоской карты (см. Граф плоский )раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?

Гипотеза о том, что ответ на Ч. к. з. утвердительный, была сформулирована в сер. 19 в. В 1890 было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку Ч. к. з. в терминах графов: верно ли, что хроматич. число (см. Графа, раскраска )любого плоского графа G не превосходит Многочисленные попытки решения Ч. к. з. оказали влияние на развитие ряда направлений графов теории. В 1976 анонсировано положительное решение Ч. к. з. с использованием ЭВМ (см. [3]).

Лит.:[1] Xарари Ф., Теория графов, пер. с англ., М., 1973; [2] Ore О., The four-color problem, N. у.- L., 1967; [3] Арреl К., Нakеn W., лIII. J. Math.