# m-Coloring Problem

# Introduction

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.

# Dependencies

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

# Data

# Solution

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)

## Aim

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

## Extra

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)

## Aim

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

# plot_choropleth(colormap: dictionary)

## Aim

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

# Logic

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

**Result**

# Full Code

`https://github.com/asrinoztin/m-coloring`