ISSN 2079-3537      


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,

2 ORCID: 0000-0002-9472-3351,

3 ORCID: 0000-0002-7257-9029,



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.