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

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