Scientific Visualization, 2018, volume 10, number 3, pages 1 - 33, DOI: 10.26583/sv.10.3.01
Visual algorithm for coloring planar graphs
Authors: S.V. Kurapov1,A, M.V. Davidovsky2,A, A.V. Tolok3,B
A Zaporozhye National University, Ukraine
B Moscow State Technological University «STANKIN», Russia
1 ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru
2 ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com
3 ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru
Abstract
This article addresses a plane graph coloring problem. The authors propose a new visual algorithm for coloring planar graphs and present a deductive proof of the four-color theorem which is based on the properties of the Klein four-group. It is shown that an arbitrary colored cubic graph has three colored 2-factors and the addition of colors is done according to the laws of the Klein four-group transformation. The properties of colored plane cubic graphs are considered. Two theorems about the existence of a colored disk passing through linked edges and about edge coloring of a plane cubic graph are formulated and proved in the article. Moreover, it is shown that the four-color theorem can be obtained as a consequence of these proved theorems. In order to allow edge recoloring in a colored plane cubic graph the authors introduce a new operation – the rotation of a colored disk. The article provides examples of solving the problem of planar graphs coloring.
Keywords: graph, graph coloring, maximal planar graph, isometric cycles, Klein four-group, graph factors.
