Раскраска плоских графов. Теория, методы, алгоритмы

📙 В данной работе доказывается теорема о существовании цветного диска в плоском кубическом графе, проходящего по двум сцепленным рёбрам, принадлежащим изометрическому циклу или ободу графа. На основе доказанной теоремы представлены алгоритмы раскраски плоских кубических графов в три цвета. Kurapov S. V., Davidovsky M. V. The Coloring of Plane Graphs. Theory, Methods and Algorithms. In this monography we prove a theorem on the existence of a colored disk passing through the two linked edges belonging to an isometric cycle or a rim in a plane cubic graph. On the basis of the proved theorem the algorithms of planar graphs edge coloring with three colors are presented.