GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
823 views

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

  1. 2
  2. 3
  3. 4
  4. 5
asked in Graph Theory by Veteran (66.2k points) 1154 2199 2522 | 823 views

graph is planar so we can directly say it requires not more than 4 color

this graph has also odd length cycle for that 3 color requires

also this graph has even length cycle for that 2 color 

but i have a doubt here :

if graph is very complex and if both the even and odd length cycle appears as well as planar solution then whts the correct aproach to find color requirement in graph 

same situation with this http://gateoverflow.in/3263/gate2008-it-3

@Bikram sir which approach ?pls help

 

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

We can use this approach here.

as it is maximum 4 , then 4 colors require for complex kind of graphs where both the even and odd length cycle appears as well as planar solution ..

4 Answers

+11 votes
Best answer

4 colors are required to color the graph in the prescribed way.

answer = option C

answered by Veteran (29.3k points) 75 220 379
selected by
Practical approach :)
Here we also need to prove that the given graph can't be colored with less than 4 colors.

As it consists cycle with odd vertices it requires at least 3 colors.

But if you try to color them with 3 colors it is not possible to color them with 3 colors.

More ever any planar graph can be colored with 4 colors (Four color theorem).
+2 votes

Ans C 

answered by Veteran (10.7k points) 15 62 101
0 votes
note:-The max degree of the vertex is 4 so we need atmost 4 colours to colour the graph

answer is C) 4 only
answered by Boss (5.4k points) 17 42 62
edited by
–3 votes
The max degree of the vertex is 4 so we need atleast 5 colours to colour the graph
answered by Veteran (13.6k points) 15 70 142
4 colours are enough here !
It is a planar graph so we need only 4 colour.
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23356 Points

  2. Bikram

    17058 Points

  3. Habibkhan

    8142 Points

  4. srestha

    6254 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4298 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Popular Question Sonali Rangwani
Notable Question Sandeep Suri
100 Club stdntlfe
Nice Question thor
100 Club Vamp thehacker
Popular Question LavTheRawkstar
Notable Question shubham vashishtha
Nice Answer Habibkhan
Good Question jenny101
Regular Ashish Subscription
27,302 questions
35,156 answers
83,985 comments
33,244 users