855 views
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.

### 1 comment

while coloring a graph,try to use already used colors.think a while can i use the used colors.I think it will give correct answer in most of the cases.

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.

Ayush do you have any algorithm to find the maximal independent sets in a graph.

Because if you don‘t have any algo you can't be sure that you will always find the minimum chromatic partition in a graph.
@Kushagra-Yes I read one algorithm in Narsingh Deo, it's based on boolean algebra simplification and it gets cumbersome even with a graph with 5 vertices.

What I do is I start constructing maximal independet set taking each vertex one by one

Like say here in this problem only I first start with vertex a

Now I got a and now I will make all independent sets of vertices that can go with a.

So, with a I can have {a,d} and {a,f}.

With b I can only have {b,e}

With d I can have {d,a}(already included) and {d,e} and so I do for the remaining vertices.

So, this method is what I found faster to work with.
Look what I know is finding chromatic number in a graph is a np - complete problem.

So, there should not exist any polynomial time algorithm that will find chromatic number of a graph under all conditions.

May be there are some good polynomial time techniques that work for most of the graphs but it should not work in all conditions.

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.

@shaik

Finding the chromatic number in a graph is a np - complete problem.

So,there does not exist any polynomial time algorithm for finding chromatic number of a graph.

So, if your algorithm is taking polynomial time then it has to be wrong.
yes, I agree that... but finding all cycles in a undirected graph is a exponential algorithm... that leads my algorithm is not polynomial

But in gate or some other competitive exams we can easily find total cycles in a graph... it's make my procedure simple. Isn't i'm right bro ?
Yes I think you are right.

1
1,580 views