First time here? Checkout the FAQ!
+2 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 (87.2k points)   | 155 views

1 Answer

+4 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 Active (1k points)  
selected by

Top Users Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points

26,060 questions
33,668 answers
31,079 users