GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
698 views

What is the chromatic number of the following graph?

GATE2008-IT_3

  1. 2
  2. 3
  3. 4
  4. 5
asked in Graph Theory by Veteran (20.9k points)  
edited by | 698 views

1 Answer

+12 votes
Best answer

The chromatic number of a graph  is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.

Hence minimum number of colors needed to color given graph is equal to 3( option 2

For odd length cycles we need minimum 3 colors for vertex coloring and for even length cycles we need just 2. 

answered by (367 points)  
selected by
how do we differentiate between regular and planar graph to calculate chromatic number.

Like for planar graph we have chromatic number 4. whereas if we have odd cycles chromatic number = 3 else for even it is 2.

Please help.
chromatic number of cycle graph if it is planar

3 if n is odd

2 if n is even

chromatic number of wheel graph if it is planar

3 if n is odd

4 if n is even

The Four Color theorem

The chromatic number of a planar graph is no greater than four.

Using this we can rule out some option directly. 



Top Users Sep 2017
  1. Habibkhan

    7838 Points

  2. Warrior

    2812 Points

  3. Arjun

    2696 Points

  4. rishu_darkshadow

    2692 Points

  5. A_i_$_h

    2456 Points

  6. manu00x

    2040 Points

  7. nikunj

    1980 Points

  8. Bikram

    1864 Points

  9. makhdoom ghaya

    1790 Points

  10. SiddharthMahapatra

    1718 Points


26,243 questions
33,815 answers
80,261 comments
31,168 users