GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
124 views

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 (78.4k points)   | 124 views

1 Answer

+3 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' .

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.

Therefore, option c is correct.
answered by Junior (965 points)  
selected by


Top Users Jul 2017
  1. Bikram

    5784 Points

  2. manu00x

    3602 Points

  3. Arjun

    1988 Points

  4. Debashish Deka

    1924 Points

  5. joshi_nitish

    1908 Points

  6. pawan kumarln

    1680 Points

  7. Tesla!

    1426 Points

  8. Hemant Parihar

    1334 Points

  9. Shubhanshu

    1180 Points

  10. Arnab Bhadra

    1124 Points


24,169 questions
31,186 answers
71,039 comments
29,512 users