GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
1.5k views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
asked in Graph Theory by Veteran (41.3k points)  
edited by | 1.5k views

For PLANAR  GRAPHS There are........

vertex colouring for vertices

map colouring for regions

and

edge colouring for edges

IN THE QUESTION planar graph requires ( MINIMUM ) vertex colouring .

1)

DRAW A GRAPH WITH 2 VERTICES AND ONE EDGE

( ie.,  v=2 , e = 1 , f =1 )  IS  A PLANAR GRAPH .

AND IT SATISFIES EULER FORMULA  .( v - e + f  = 2 )

The  minimum Colours  it require = 2.

2)

Take a rectangle with out diagonals .

Is a planar graph  AND   by vertex colouring it requires  2  colors .

 

THE MINIMUM NO OF COLOURS SUFFICIENT  TO  vertex colour   ANY  planar graph  = 2

In above question ANY plannar graph is said. Means you need to find the maximum no. of vertex-color among all the planner graph. And that maximum no will be the minimum no of color that is sufficient to vertex-color any planer graph.

Take a Triangle you will required 3 color.

PLSE

GIVE AN EXAMLE GRAPH
In any planar graph ,

consider a tree

 every tree is a planar grapgh and it is triangle free graph

a tree with n vertices requires 2 colours.

for example

 a tree with 100 vertices having 99 edges , it requires minimum two colours.
You need to consider every planner graph. Triangle is also a planner graph but you can't color it with 2 color. You need 3. which implies 2 color is not sufficient to color any planner graph.
It is little bit language problem. Just read the comment given below the selected answer.

yes 

ANY plannar graph  Means we need to find the maximum no. of vertex-color among all the planner graphs And that maximum no will be the minimum no of color that is sufficient to vertex-color any planer graph.

answer is 4

 

4 Answers

+17 votes
Best answer

Four colour theorem is famous result, it says that any planar graphs can be coloured with only 4 colours !

Ref -> https://en.wikipedia.org/wiki/Four_color_theorem

 

Note for confused people => laugh

 
Here ANY is used in sense of FOR ALL x , so , here ANY means literally any one of graph can be selected !

What are you saying , is something like There exists, but in that case, they will say, That specific graph directly..

Any man alive is gonna die => This means all men are gonna die ! Not specific to anyone !
Hope this clears thing a bit !
answered by Veteran (41.3k points)  
selected by
actually ..I have a question ..null graph is also considerd as planer ..but we can't color null graph with 4 colors?? I think here any is an ambiguous word ..the answer might be 4 but this null graph thing I dont understand..

@abhi150

Hope that you got your answer :) Check answer again !

ok ...got it thanks
i have a question,

planar graphs not in syllabus right ?
I have one doubt the theorem states that no more than 4 colors are required but the ques is asking for minimum, is it not contradictory? I mean if we take two points and join them it can be colored using 2 colors. I am not including single point as disconnected graphs are not considered for coloring. @Akash Kanase @Arjun
even I thought the same ..Null graph is also planer but we can color that by only 1 color..but I think the question here says sufficient to vertex color "any" planer graph ..with just 1 or 2 colors we can't color K4 ..although it would have been much better if they had not used "any" .Any is used as For all x but we should always avoid using Any as it is ambiguous.
Okay so it means min for worst case scenario.. Got it thanks :)
Question is confusing.. At the most 4 colours are used..interpretation of question could vary from person to person :)
But knowing English grammar is also necessary for GATE.
Yeah English and context free too :P
+4 votes
According to four color theorem, Every planar graph can be colored using 4 colors.
answered by Junior (717 points)  
0 votes
@arjun sir : can you verify

as far i know , 4 is neccessary to colour any graph (planar )

but 5 is sufficent one

but since they have asked minimum colour so it should be 4 right ?

Ref : Narisngh deo book
answered by Boss (9.5k points)  
0 votes

For PLANAR  GRAPHS There are........ 

vertex colouring for vertices 

map colouring for regions 

and 

edge colouring for edges 

IN THE QUESTION planar graph requires ( MINIMUM ) vertex colouring . 

1) 

DRAW A GRAPH WITH 2 VERTICES AND ONE EDGE 

( ie.,  v=2 , e = 1 , f =1 )  IS  A PLANAR GRAPH . 

AND IT SATISFIES EULER FORMULA  .( v - e + f  = 2 ) 

The  minimum Colours  it require = 2. 

2) 

Take a rectangle with out diagonals . 

Is a planar graph  AND   by vertex colouring it requires  2  colors .

 

THE MINIMUM NO OF COLOURS SUFFICIENT  TO  This  planar graph  = 2

 

ALSO 

In any planar graph ,

consider a tree 

 every tree is a planar grapgh and it is triangle free graph 

a tree with n vertices requires 2 colours.

for example 

 a tree with 100 vertices having 99 edges , it requires minimum 2 (two ) colours.

3)

consider a triangle  with 3 vertices & 3 edges

it requires  minimum 3 colours 

4)

consider a wheel graph of 4 vertices 

it requires  minimum 4 colours 

5)

cosider  a complete graph of 4 vertices  (k4)

it requires  minimum 4 colours 

 

6)cosider  a complete graph of 5 vertices  (k5)

it requires  minimum 5 colours with respect to vertex colour , but  k5 is NON PLANAR 

 

IN THE GIVEN QUESTION 

ANY plannar graph  Means we need to find the maximum no. of vertex-color among all the planner graphs And that maximum no will be the minimum no of color that is sufficient to vertex-color any planer graph.

SO

                              answer is 4

 

answered by (95 points)  
edited by


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arunav Khare

    1464 Points

  10. Arjun

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,062 answers
63,294 comments
24,160 users