Раскраски

Гипотезу четырех красок можно с полным основанием назвать еще «болезнью четырех красок», так как она во многом похожа на заболевание. Она в высшей степени заразна. Иногда она протекает сравнительно легко, но в некоторых случаях, приобретает затяжной или даже угрожающий характер. Никаких прививок против нее не существует; правда, люди с достаточно здоровым организмом после короткой вспышки приобретают пожизненный иммунитет. Этой болезнью человек может болеть несколько раз, и она подчас сопровождается острой болью, но ни одного летального исхода зарегистрировано не было. Известен, по крайней мере один случай передачи болезни от отца к сыну, так что, может быть, она наследственна.

Тем не менее, именно попытки обосновать эту гипотезу стимулировали получение ряда результатов по раскраске графов, которые в свою очередь привели к исследованиям некоторых других разделов теории графов.

В этой главе после определения раскраски графа и его хроматического числа излагается доказательство теоремы о пяти красках, а затем обсуждается гипотеза четырех красок. Далее вводятся однозначно раскрашиваемые графы, т. е. графы, которые можно раскрасить единственным образом, а также критические графы (минимальные относительно раскраски). Исследуется тесная взаимосвязь между гомоморфизмами и раскрасками. Глава завершается описанием свойств хроматического многочлена.