GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
388 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 (19k points)  
edited by | 388 views

1 Answer

+11 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
Top Users Feb 2017
  1. Arjun

    5288 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3952 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. mcjoshi

    1690 Points

  10. sh!va

    1684 Points

Monthly Topper: Rs. 500 gift card

20,860 questions
26,010 answers
59,673 comments
22,113 users