closed by
1,331 views
1 votes
1 votes
closed with the note: Doubt Resolved

This has reference to the below question

https://gateoverflow.in/204092/gate2018-18?show=204092#q204092

My doubt is 

Suppose, I try to colour the vertices of this graph as follows

  • First I colour vertex a and f with colour 1.
  • Then I colour vertex e and b with colour 2.
  • Now when I move to colour vertex c and d, it appears to me now that I need 4 colours.

But the chromatic number of this graph is 3.This was the mistake I did in GATE exam.

Please, anyone help me know what is exactly wrong with my approach and how what points in mind do I need to remember so that I can colour any given graph with the minimum number of colours.

closed by

2 Answers

3 votes
3 votes

The algorithm that you applied is Greedy Algorithm. But Optimal solution of Graph coloring for some graphs depends on From which Vertex you start if you use Greedy Algorithm. Try on this Graph. Start with vertex $c$ and give it color $1$, then visit its adjacent vertex $d$ and color it with color $2$ and then visit next vertex $b$ and color it with color $3$ then visit vertex $a$ and color it with color $2$(because that is the minimum number available for vertex $a$) then visit vertex $e$ and give it color $3$, then visit vertex $f$ and give it color $1$(because it is the minimum number available for $f$).... This Ordering will give your greedy algorithm a Optimal solution. That's why we can say that Graph coloring is not an application of Greedy algorithm. 

Wikipedia on Greedy algorithm for Graph Coloring : 

The greedy algorithm considers the vertices in a specific order $v_1, v_2, v_3...,v_n$ and assigns to $v_i$ the smallest available color not used by $v_i$’s neighbours among $v_1.....v_{i-1}$, adding a fresh color if needed. The quality of the resulting coloring depends on the chosen ordering. There exists an ordering that leads to a greedy coloring with the optimal number of  colors. On the other hand, greedy colorings can be arbitrarily bad; for example, the crown graph on n vertices can be 2-colored, but has an ordering that leads to a greedy coloring with $n/2$ colors. 

The maximum (worst) number of colors that can be obtained by the greedy algorithm, by using a vertex ordering chosen to maximize this number, is called the Grundy number of a graph.

 So, We would need to apply Dynamic Programming for Graph coloring. But that takes time as we know. So, Some guidelines could be used :

1. If you find some Cycle of Three vertices in the Graph, then start from there and give each vertex a different color Because that would be necessary, doesn't matter how you color the Graph.

2. If the Graph is Planar then Optimal number can never exceed $4$. (The Four color theorem "Every planar graph can be colored with maximum $4$ colors.)

Other useful guidelines are welcome if someone has.

0 votes
0 votes

According to my approach, first color High degree vertices....

prepare a stack push the elements into ascending order of their degree's 

              i.e., high degree vertices is the top of the stack

the order we have to color is c,b,a,d,e,f may be permutation lead to any of 2*4!=48. take any one.

first color all vertices with c1

let pop one high degree vertex ( vertex c ) , color all its adjacent vertices to c2

let pop one more high degree vertex ( vertex B ), color all its adjacent vertices which are conflicting ( which are in the stack only by this property we can not disturb previously allocated colors to vertices which are high degree than currently poped vertex ) to c3.

continue this process until there is conflict.

edited by

Related questions

0 votes
0 votes
1 answer
1
Sahil_Lather asked Apr 15, 2023
439 views
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ .The find the minimum number of colours required ot edge-colour is ...
4 votes
4 votes
2 answers
2
Balaji Jegan asked Nov 27, 2018
2,486 views
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ?There is a condition that adjacent...
3 votes
3 votes
1 answer
3
0 votes
0 votes
0 answers
4
dan31 asked Nov 6, 2018
1,197 views
If G is a connected k-regular graph with chromatic number k+1, then find the number of edges in G?