in Graph Theory edited by
11,561 views
36 votes
36 votes
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
in Graph Theory edited by
11.6k views

4 Comments

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.
5
5

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

0
0
The graph K(3,2) or Complete Bipartite graph Is Planar But has a chromatic number 2 . Can some one tell me why the answer to this question is not 2 and is 4?
0
0

5 Answers

65 votes
65 votes
Best answer

Four color theorem is a famous result and it says that any planar graphs can be colored with only $4$ colors.

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

Note for confused people  😄

Here ANY is used in sense of FOR ALL $x$. i.e., ANY means literally any one of graph can be selected !
Any man alive is gonna die $\Rightarrow$ All men are gonna die and not any specific one.

Hope this clears thing a bit !

edited by

4 Comments

Interestingly, the original four color theorem was about coloring the regions of a planar graph. Narsingh Deo states that a graph has a dual if and only if it is planar, therefore coloring regions of a planar graph $G$ is equivalent to coloring the nodes of its dual $G^*$, and vice versa.

So the four color theorem can also be restated in terms of nodes instead of regions.
0
0

Theorem 5.10.6

(Five Color Theorem) Every planar graph can be colored with 5 colors.

REF : https://www.whitman.edu/mathematics/cgt_online/book/section05.10.html

Why here it is showing 5 colors??

0
0

see here it is saying a planar graph is  4-colorable , 5- colorable as well as 6- colorable.

-> http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/MatthewWahab/theorems.html

and I think it is obvious that if a graph is 4 colorable then we can color it easily with more than 4 colors as well (as many vertices it have)!

0
0
6 votes
6 votes
According to four color theorem, Every planar graph can be colored using 4 colors.
6 votes
6 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

edited by
4 votes
4 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.
Answer:

Related questions