# Graph Coloring Algorithm – Computer Science Stack Exchange

I have a simple graph G = (V,E) and each vertex has a range (a,b).Every two vertices are connected only if (a_1,b_1) and (a_2,b_2) have a common subrange.

Each range of vertex is rV1 = (0,5) rV2 = (1,3) rV3 = (2,10)
rV4 = (4,9) rV5 = (6,7) rV6 = (8,12) rV7 = (11,13)

Graph Created based on above ranges.

Based on the algorithm below i have to color the graph.

``````ranges = rV1,rV2,rV3,rV4,rV5,rV6,rV7...

COLOR_INTERVAL_GRAPH(rV1,rV2,rV3,rV4,rV5,rV6,rV7...){
if(number of rVi > 0){
C_m  = MAXIMAL_COLOR_CLASS(rV1,rV2,rV3,rV4,rV5,rV6,rV7...);
//paint C_m vertices with color m.
//new_ranges <- remove C_m from rV1,rV2,rV3,rV4,rV5,rV6,rV7...
return {C_m} U COLOR_INTERVAL_GRAPH(new_ranges)
else:
return ()

MAXIMAL_COLOR_CLASS(new_range){
C = ()
i = 1
while(i <= new_range.size()){
C = C U {Vi}
j = i+1
while(j <= new_range.size() AND rVi (not common subrange with rVj)){
j = j+1
i=j
return C
``````

Question 1: Is the algortihm greedy, and used it to color the graph given above.

Answer 1: The algorithm has the ‘greedy choice property’ since it paints the most each turn, by choosing the best solution to the current subproblem without caring about future problems or backtracking. (Is my reasoning correct?).

Graph Colored (Is the graph colored correctly?).

Question 2: Prove using induction that the algorithm uses the fewest possible colors.

Answer 2: The MAXIMAL_COLOR_CLASS function in line 4 extends the C set.I have to prove that the optimum coloring of any graph (of this type) can be transformed in order the first chromatic class is the same as the output of MAXIMAL_COLOR_CLASS.
Then using the above (by induction) i can show that every optimum coloring is the same as the output of the MAXIMAL_COLOR_CLASS proving the algorithm correct. Not sure how to use induction to prove that.

Question 3: Convert the algorithm from recursive to iterative form.

Answer 3: MAXIMAL_COLOR_CLASS stays the same, the COLOR_INTERVAL_GRAPH is transformed to:

``````COLOR_INTERVAL_GRAPH(ranges){
m=1
while(ranges.size() > 0){
C_m = MAXIMAL_COLOR_CLASS(ranges)
matrix <- C_m + "," + m //meaning ((1,5,6),1) ((2,4,7),2) ((3),3) in the example above
sequence = remove the C_m vertices from sequence //(sequence - C_m)
m = m + 1
}return matrix
``````

Question 4: Instead of MAXIMAL_COLOR_CLASS now the algorith uses FIRST_LAST_CLASS which outputs a set of vertices that has the vertex with the smallest starting range and the vertex with the biggest ending range (remember (start,end)), where the last is not crossing the first. Show an example where this form of algorithm uses more colors than needed.

Answer 4: In the graph given above this algorithm needs 4 or 5 colors since each C set can have at most 2 colors, however we know the graph can be colored using 3 colors instead. (Is my reasoning correct?).

Posted on