m-Coloring Problem

asrın öztin
3 min readJun 1, 2021


m-Coloring is a problem which is basically in order to determine/show that if we manage to color a graph with at most m colors such that no two adjacent vertices of the given graph are colored with the same color.

There are three common ways to solve that kind of problem. These,

1. Naive Appoach

Can be thought as a brute-force way. It is based on the idea that “on worst case scenario it will take m^n tries with m colors and n vertices given”. Thus the time complexity is O(m^n) and space complexity is O(n).

2. Backtracking

The main purpose of this algorithm is to reach the goal with learning from repetition and it’s own mistakes. As the name suggests, the algorithm takes a step back to find a solution. At first the algorithm starts with a possible move and then keeps going with another. If it does not satisfy, algorithm goes back and tries another one, until it either finds a solution or appears that there is no solution. Thus the time complexity is O(m^n) and space complexity is O(n). The upperbound time complexity (worst-case scenario) is same with brute-force navive approach since there is a total combination of vertex colors is same as m^n. On the other hand, the average complexity is lower relatively.

3. BFS:

The appoarch with BFS is based on the idea that coloring each node from 1 to n travelling with BFS. The algorithm checks all edges of the given node and if the color of the neighbors are same, corrects it and goes on. Time complexity is linear and the space complexity is O(V) since it stores the visited nodes.


In order to run the functions, you need to install the following modules into your virtual environment

▪ pandas (current latest version: 1.1.4)

▪ plotly (current latest version: 4.13.0)

Constraint Satisfaction Problems (CSPs)

Task: Color each region

Variables: X = {Argentina, Bolivia, Brazil, Chile, Colombia, Ecuador, Falkland Islands, Guyana, Paraguay, Peru, Suriname, Uruguay, Venezuela}

Domains: Di = {blue, red, green, yellow}

Constraints: adjacent regions must have different color



Solution can be handled with 3 functions basically. At first we declare a list to use later just to reach countries when iterating.

k_list = list(adj)

color_w_backtracking(k: integer)


The function is in order to create the result dictionary by checking neighbors’ colors for each counrty.


This part of the code can also be handled with another “for loop”. However, for the sake of simplicity, it is handled with iterating manually with the constant “k” by calling the function with parameter = 0.

check_safe(curr_country: String, curr_color: String)


The fuction is in order to check if a color is allowed (still available) to assign to a country.

plot_choropleth(colormap: dictionary)


The function is in order to visualize the map by result dictionary.


To understand the algorithm better, print(information_about_that_step) is used at important breakpoints.


Full Code




asrın öztin

Computer Science Engineering educated, with interest in Data Science.