Раскраска замкнутых поверхностей и теория графов

Теорема Эйлера и теорема Хивуда помогают определить вид поверхности по числовым характеристикам. Нахождение количества цветов, необходимых для раскраски замкнутых поверхностей можно проводить как раскраской областей, так и раскраской вершин уложенных графов. Анализируя значения эйлеровой характеристики, полученной для рассматриваемых поверхностей, был сделан вывод, что для однозначного определения поверхности этого недостаточно. Хроматическое число однозначно определяет вид замкнутой поверхности, если хроматическое число графа, построенного на поверхности, совпадает с “хроматическим номером” поверхности. Поиск правильной раскраски графа помогает решать целый ряд практических задач: задача о составлении расписания, об экономии памяти, о распределении ресурсов.