can anyone tell me about the application of vertex coloring problem and algorithm for vertex color problem in graph or networks.
1
-
$\begingroup$ Please correct the question title (title is on dominating set, but the question in on coloring). $\endgroup$– Cyriac AntonyFeb 9 at 6:19
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Vertex coloring is useful in grouping. Suppose you have hazardous chemicals that cannot be stored together. What is the minimum number of storage units you need to store all your chemicals? Similarly, suppose you have a set of volunteers and certain volunteers who won't work with each other. How do you group them to minimize the number of groups?
Dominating sets are useful in routing problems. How many internet routers do you need so that every computer in your business has internet access?
$\begingroup$
$\endgroup$
It is also useful in scheduling problems. Suppose that some people are attending a conference. Each person writes down a list of events they want to attend. What is the smallest number of time slots needed so that everyone can attend all sessions that they want to attend (assuming there are enough rooms)? Make a graph whose vertices are the different events, with an edge between two vertices $x$ and $y$ if there is at least one person who wants to attend events $x$ and $y$. The smallest number of events is the chromatic number of the graph.
One of the earliest colouring problems is in map colouring. What is the smallest number of colours needed to colour a map so that no two neighbouring countries have the same colour? Make a graph where the vertices are the countries, states/provinces, counties, or whatever your sub-region of interest is. Two vertices are adjacent if the corresponding subregions share a border. The smallest number of colours needed to colour the map is the chromatic number of the graph (this is probably why we refer to it as a colouring)
You could think of a Sudoku puzzle as a type of colouring problem. Each of the 81 boxes in the puzzle is a vertex. Two vertices are connected by an edge if they are in the same row, column, or one of the nine $3\times 3$ subsquares. Some of the vertices have already been assigned "colours" 1 through 9. To solve the puzzle, you must colour the remaining vertices with colours 1 through 9 so that no two adjacent vertices have the same colour.
