New Results about the Structure of Plane Graphs: a Survey

摘要

One of the central areas of graph theory is coloring, which is partitioning discrete objects into simpler sub-objects. The development of the theory of planar graphs coloring, as well as that of graph theory as a whole, was initiated by attempts to solve the famous Four Color Problem, solved in 1976 by Appel and Haken. New results on planar graphs coloring are usually based on establishing more subtle structural properties of planar graphs. In 2013-2017, we published with our co-authors 34 papers concerning the structure of paths, faces, stars, and cycles, most of which give tight results. In particular, we have confirmed or disproved several long-stood conjectures.