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

Abstract

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”.