GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
509 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 (19.2k points)  
edited by | 509 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.


Top Users May 2017
  1. akash.dinkar12

    3568 Points

  2. pawan kumarln

    2206 Points

  3. Bikram

    1940 Points

  4. sh!va

    1682 Points

  5. Arjun

    1650 Points

  6. Devshree Dubey

    1272 Points

  7. Debashish Deka

    1270 Points

  8. Angkit

    1056 Points

  9. LeenSharma

    1028 Points

  10. Arnab Bhadra

    904 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    1026 Points

  2. pawan kumarln

    832 Points

  3. Arnab Bhadra

    818 Points

  4. akash.dinkar12

    448 Points

  5. Arjun

    378 Points


22,897 questions
29,213 answers
65,336 comments
27,713 users