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

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

 

5 Answers

+19 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.9k 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.7k 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 (105 points)  
edited by
0 votes
If we talk about minimum no. of colors that is sufficient to vertex-color in any planar graph which means a planar graph with any no. of vertices. However, in some cases, 3 colors are suffcient to vertex-color in a planar graph like triangle whereas in some cases 4 colors are suffcient to vertex-color in a planar graph . But is has been proved that 4 colors are sufficient to vertex-color every planar graph. It is called as the four color theorem. So, the answer will be 4.
answered by (11 points)  


Top Users Jul 2017
  1. Bikram

    4910 Points

  2. manu00x

    2940 Points

  3. Debashish Deka

    1870 Points

  4. joshi_nitish

    1776 Points

  5. Arjun

    1506 Points

  6. Hemant Parihar

    1306 Points

  7. Shubhanshu

    1128 Points

  8. pawan kumarln

    1124 Points

  9. Arnab Bhadra

    1114 Points

  10. Ahwan

    956 Points


24,099 questions
31,074 answers
70,703 comments
29,407 users