The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
153 views
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?
asked in Graph Theory by Veteran (98k points) | 153 views

4 Answers

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

So, Chromatic number will be 3
answered by Veteran (70.1k points)
+3 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

 

answered by Veteran (10.4k points)
0 votes
for odd no of vertices of cycle graph chromatic no is 3.
answered by Loyal (3.7k points)
0 votes

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

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

answered by Active (2.2k points)


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

29,017 questions
36,844 answers
91,380 comments
34,721 users