Математическая энциклопедия - четырех красок задача

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

Гипотеза о том, что ответ на Ч. к. з. утвердительный, была сформулирована в сер. 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.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985