recategorized by
1,576 views
0 votes
0 votes

Consider the following statements:

  1. Any tree is $2$-colorable
  2. A graph $G$ has no cycles of even length if it is bipartite
  3. A graph $G$ is $2$-colorable if is bipartite
  4. A graph $G$ can be colored with $d+1$ colors if $d$ is the maximum degree of any vertex in the graph $G$
  5. A graph $G$ can be colored with $O(\log \mid v \mid )$ colors if it has $O(\mid v \mid )$ edges.

Choose the correct answer from the options given below:

  1. $(iii)$ and $(v)$ are incorrect
  2. $(ii)$ and $(iii)$ are incorrect
  3. $(ii)$ and $(v)$ are incorrect
  4. $(i)$ and $(iv)$ are incorrect
recategorized by

1 Answer

0 votes
0 votes
  1. Any tree is 2-colorable     True every tree is bipartite graph with chromatic number 2
  2. A graph G has no cycles of even length if it is bipartite False e.g cycle of length 4 
  3. A graph G is 2-colorable if is bipartite True
  4. A graph G can be colored with d+1 colors if d is the maximum degree of any vertex in the graph G True     as vertex of degree d means it is adjacent to d vertices hence need d+1 different colors 
  5. A graph G can be colored with O(log∣v∣) colors if it has O(∣v∣) degrees False as Kn has O(n^2) edges with chromatic number n      so it need O (√ V) colurs 

Hence ans is option C) (b) and (e) are incorrect

Answer:

Related questions