ABSTRACT
Graph coloring is a well-known NP-complete problem in discrete mathematics. The problem is classified as combinatorial optimization and has three main subproblems: node coloring, edge coloring, and face coloring. In node coloring, or vertex coloring, the problem is to minimize the number of colors needed to color the nodes of a connected graph in such a way that no two adjacent nodes share the same color. In a similar manner, edge coloring is the problem of coloring the edges in such a way that no two edges sharing the same node are assigned with the same color. In general, edge coloring becomes node coloring by mapping the graph to a new graph where the edges of the first graph are the nodes of the second graph. In surface coloring, the objective is to minimize the number of colors assigned to the faces (regions) of a planar graph in such a way that no two adjacent faces share the same color. Traditionally, this problem applies in map coloring where different colors are used to color bordering countries.
