Исторически понятие хроматического числа возникло с проблемой четырех красок. Проблема возникла в математике в середине 19 века. Первоначально вопрос формулировался так: сколько нужно красок для раскраски любой географической карты, при которой соседние страны раскрашены в разные цвета? Под географической картой понимается разбиение плоскости на конечное число связных областей, стран, границы которых состоят из замкнутых непрерывных линий без самопересечений, а соседними являются страны, имеющие общую границу ненулевой длины. Довольно очевидно, что четырех красок недостаточно. и вопрос формулировался обычно в более конкретном виде: достаточно ли четырех красок для раскраски любой географической карты? Это и есть проблема четырех красок. Положительный ответ на вопрос называется гипотезой четырех красок.

Проблема раскраски географических карт сводится к проблеме (правильной) раскраски плоских графов. Проиллюстрируем это сведение картой, изображенной на рис.5.9.

Рис.5.9

На рисунке изображена карта, имеющая пять стран (внешняя область - тоже страны). Внутри каждой страны зафиксируем точку, точки соединим ребром, если страны имеют общую границу. (На рис.5.9 ребра проведены пунктирными линиями). Ребра при этом можно провести так, чтобы они не пересекались, т.е. чтобы полученный граф был плоским. Ясно, что раскраска карты определяет правильную раскраску графа и обратно. Проблему четырех красок можно теперь сформулировать так: достаточно ли четырех красок для правильной раскраски плоского графа?

Эта проблема вызвала большой интерес в математике. Есть свидетельства, что ей занимались известные математики Мебиус и де Морган. В 1880 году А. Компе опубликовал положительное решение проблемы четырех красок. Однако в 1890 году Р. Хивуд обнаружил ошибку в этом доказательстве. Одновременно он показал, что пяти красок достаточно для раскраски любого плоского графа (см. §4). После этого появлялось довольно много «доказательств» гипотезы четырех красок и «контрпримеров» к ней, в которых обнаруживались ошибки. В 1969 году Х. Хели свел проблему четырех красок к исследованию множества С так называемых конфигураций. Множество с является конечным. Но довольно большим (порядка нескольких тысяч). Несколькими годами позже, в 1976 году математикам К. Аппелю и В. Хейкену удалось показать. Что все конфигурации из множества С можно правильно раскрасить в четыре цвета. В возникающем при этом переборе существенно использовался компьютер. Такое решение проблемы четырех красок долгое время не признавалось многими математиками. Поскольку его сложно повторить. Однако сейчас практически общепризнано, что К. Аппелем и В. Хейкеном доказана гипотеза четырех красок.