Application of the Four-Color Theorem for coloring a city map

  • Natasha Stojkovikj
  • Mirjana Kocaleva Computer Science Faculty, Goce Delcev University, Stip, Republic of Macedonia
  • Cveta Martinovska Bande
  • Aleksandra Stojanova
  • Biljana Zlatanovska
Keywords: graph, graph theory, maps, map coloring, algorithms


A graph can be defined as a mathematical representation of a network, or as a set of points connected by lines. By a graph can be defined all kind of transportation networks (air, rail), a telecommunication system, the internet … Graph theory is a branch of mathematics and had its beginnings in math problems. However, today it has grown into a significant area of mathematical research, with applications almost everywhere (in chemistry, operations research, social sciences, and computer science). In the paper basic definition of graph theory, then some definition of a chromatic number of a graph and certain theorems related with graph coloring are given. Then is considering the problem of map coloring with four colors. One way to consider this problem is with the theory of graphs, because graphs are closely related to maps. We considered the map of metropolitan area of Shtip and Skopje. For coloring, we use the software “Four color theorem – map solver”.


Download data is not yet available.
How to Cite
Stojkovikj, N., Kocaleva, M., Martinovska Bande, C., Stojanova, A., & Zlatanovska, B. (2020). Application of the Four-Color Theorem for coloring a city map. Balkan Journal of Applied Mathematics and Informatics, 3(1), pp. 25-36. Retrieved from