Graph Coloring

What is Graph Coloring?

Graph coloring is to assign colors to certain elements of graph subject to certain constraints

Types of Graph Coloring

1. Vertex coloring

2. Edge coloring
Coloring the edges of graph such that adjacent edges (or the edges bounding different regions) receive different colors.

3. Face coloring

-Also known as Geographical Map coloring, the idea of a coloring of the faces of a map is to assign each face of the graph a color in such a way that two faces that share an edge must get different colors.

-Faces that meet only at a vertex are allowed to be colored the same color.

Applications of Graph Coloring:

Making Schedule or Time Table

Sudoku

Map Coloring

GSM Networks

Applications: Sudoku

Each cell is a vertex

Each integer label is a “color”

A vertex is adjacent to another vertex if one of the following hold:

-Same row

-Same column

-Same 3x3 grid

Vertex-coloring solves Sudoku

Example #1

Answer

Map coloring
Color a map such that two regions with a common border are assigned different
Each map can be represented by a colors.

Each region of the map is represented by a vertex;

Edges connect two vertices if the regions represented by these vertices have a common border.

Example #2

GSM Networks

• GSM is a cellular network with its entire geographical range divided into hexagonal cells. Each cell has a communication tower which connects with mobile phones within the cell. All mobile phones connect to the GSM network by searching for cells in the immediate vicinity. GSM networks operate in only four different frequency ranges. The reason why only four different frequencies suffice is clear: the map of the cellular regions can be properly colored by using only four different colors! So, the vertex coloring algorithm may be used for assigning at most four different frequencies for any GSM mobile phone network

Example # 3