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

2 Answers

+12 votes
Best answer

i. 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}$

ii. is false since cyles with odd no of vertices require 3 colours.

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

answered by Active (1.5k points)
edited by
+2 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

answered by Veteran (11.2k points)
edited by

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

33,716 questions
40,263 answers
38,900 users