775 views
1 votes
1 votes
A proper vertex colouring of a graph $G$ is a colouring of the vertices in $G$ in such a way that two vertices get different colours if they are adjacent. The minimum number of colours required for proper vertex colouring of $G$ is called the chromatic number of $G$. Then what is the chromatic number of the cycle graph on 149 vertices?

4 Answers

6 votes
6 votes
As there are odd number of vertices in the cycle graph

So, Chromatic number will be 3
5 votes
5 votes

THE FORMULA FOR CROMATIC NUM OF CYCLIC GRAPH IS

       N - 2(FLOOR(N/2))  + 2

EG : FOR TRIANGLE(3 CYCLE) WE NEED 3 COLOUR AND FORMULA GIVES   3(PUT N=3)

        FOR SQUARE(4 CYCLE) WE NEED =2 COLOURS AND FORMULA GIVES 2

FOR 149 IT WILL BE

              149-2(FLOOR(149/2))+2

            =149-2*74 +2 =149-148+2=3

 

2 votes
2 votes

For Cyclic Graph 
if no. of vertices = even then  Chromatic number is

if no. of vertices = odd then  Chromatic number is 3

Related questions

0 votes
0 votes
2 answers
1
go_editor asked Jun 8, 2016
447 views
Which of the following statement(s) is(are) true?If $n$ is odd prime number then $2^{n-1} \text{ mod } n =1$If $2^{n-1} \text{ mod } n =1$ for a number $n$ then $n$ is pr...
2 votes
2 votes
1 answer
2
go_editor asked Jun 8, 2016
335 views
Write the truth table for the connective: "If A then B"
0 votes
0 votes
3 answers
3