in Graph Theory edited by
2,729 views
23 votes
23 votes

A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements:

  1. If every vertex in $G$ has degree at most $d$ then $G$ admits a vertex coulouring using $d+1$ colours.
  2. Every cycle admits a vertex colouring using $2$ colours
  3. Every tree admits a vertex colouring using $2$ colours

Which of the above statements is/are TRUE? Choose from the following options:

  1. only i
  2. only i and ii
  3. only i and iii
  4. only ii and iii
  5. i, ii, and iii
in Graph Theory edited by
2.7k views

2 Answers

23 votes
23 votes
Best answer
  1. is true, since in worst case the graph can be complete. So, $d+1$ colours are necessary for graph containing vertices with degree atmost $'d'$ . Example : Consider a complete graph of $4$ vertices ... $K_{4}$
     
  2. is false since cyles with odd no of vertices require $3$ colours.
     
  3. is true, since each level of the tree must be coloured in an alternate fashion. We can do this with two colours. Its a theorem that a tree is $2$ colourable ...


Therefore, option C is correct.

edited by

4 Comments

for this graph, the chromatic number is 3 only even though each vertex has atmost 4 degree..which is negating the option a. (atmost here means not every vertex needs to have degree 4 right)..correct me if i am wrong

1
1
edited by

@chandra sai how is it $3$? It's $4$ I think. 

Also, if I can color a graph using $3$ colors, I can also color the same graph using $4,5,6,...n$ colors.

So, your graph is not negating the option at all.  

0
0

@tarun_svbk 1 doubt For a square each vertex has a degree 2 we can convert the graph into a bipartite graph so here it is 2 colorable so how (i) is correct

0
0

@Pratyush Priyam Kuan here d + 1 is not minimum no. of colors required ( i.e. Chromatic no. ) it just says that it can be surely colored using d + 1 colors which is true in your case ( we can color square using 3 colors ).

Hope you got it. :) 

0
0
4 votes
4 votes

in (i) maximum degree is 3 if A,B,C,D are colors so (3+1) colors is used 

in (ii) we can see 2 color is used but in (i) ADC is also a cycle but it requires 3 colors so not true for every cycle 

in (iii) we can see that A and B two colors are sufficient 

So option C is true i and iii is right  option

edited by

2 Comments

@Rishi yadav 1 doubt For a square each vertex has a degree 2 we can convert the graph into a bipartite graph so here it is 2 colorable so how (i) is correct

0
0
@ Pratyush

The theorem says that Chromatic number of G $\leqslant$ Max Degree of a Vertex in G (Dmax) + 1.

In other words, Chromatic number can never exceed  Dmax +1.
1
1
Answer:

Related questions

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