GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 27

Question

The chromatic numbers of the following graphs respectively are

1. Complete graph $K_{n}$.
2. Complete bipartite graph $K_{m,n}$, where $m$ and $n$ are positive integers.
3. Cyclic graph $C_{n}\:,$ where $n\geq 3$ and $n$ is odd positive integers.
4. Cyclic graph $C_{n}\:,$ where $n\geq 4$ and $n$ is even positive integers.

• A. $n,\min(m,n),2,3$
• B. $n-1,2,3,2$
• C. $n,\max(m,n),2,3$
• D. $n,2,3,2$

Answer 1

A complete graph with $n$ vertices is $n-$chromatic, because all its vertices are adjacent. So, $\chi(K_{n}) = n.$

For coloring bipartite graphs, only two colors are needed. Hence, $\chi(K_{m,n}) = 2$.

A cyclic graph $C_n$ of odd order has $\chi(C_{2n+1})=3$, and that of even order has $\chi(C_{2n})=2.$ (A cyclic graph of even order is also bipartite.)

So, the correct answer is $(D)$.