GATE CSE 2024 | Set 2 | Question: 50

Question

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is __________.

Comments

No odd length Cycles.So Bipartite: K(G)=2.

All vertices are on boundary.

Try assigning 2 Colours alternatively and check the graph.It gets satisfied with 2 colours

---

nice trick bro

---

Another beautiful method is using concept of #independent sets
https://gateoverflow.in/204092/gate-cse-2018-question-18?show=206903#a206903
Give reading to this then apply same concept here

There are two independent sets / color classes -> hence chromatic number is 2

This method is cleaner cause u don't have color graph physically

Answer 1

The given graph is bipartite, where alternating $4$ vertices can be put in one part & remaining alternating $4$ vertices in the second part.

A bipartite graph with at least $1$ edges always has chromatic number $2.$

---

To solve this question, you don't have to identify if the given graph is bipartite or not. You can directly do.

Watch Detailed Explanation: https://www.youtube.com/watch?v=fPpRg44z-yA&t=4467s

Comments

sir can we say if the graph doesn't have odd cycles then that graph is bipartite

and pls tell me how to identify planar?

@Deepak Poonia

---

@pavansan, A graph $G$ is bipartite if and only if it has no odd cycles. See HERE.

Planar Graphs Complete Explanation: https://www.youtube.com/watch?v=I0pVsAdzK0s&t=8922s

 

Answer 2

The chromatic number of the given graph is $2$.

Comments

anyone pls tell how to identify the given graph is bipartite or planar?

---

@pavansan, To solve this question, you don't have to identify if the given graph is bipartite or not. You can directly do. Watch Detailed Explanation: https://www.youtube.com/watch?v=fPpRg44z-yA&t=4467s

Answer 3

Theorem - graph is bipartite $\longleftrightarrow$ graph has no odd length cycles

notice that graph doesn't have any odd length cycles so graph is bipartite

A bipartite graph with atleast 1 edge always has a chromatic number of 2

hence answer is 2

Answer 4

Notice That There are no Nodes inside the circle , The nodes are just at the boundary , So There is no chance of formation of cycle inside the graph , It is an even length cycle with X = 2

Answer 5

The given graph is a Bipartite graph as there is no odd length cycle in the given graph

1.Bipartite graph     bi-implies    no odd length cycle.

2.Bipartite graph     bi-implies    All cycle of even length.

if given graph is bipartite and have atleast one edge then chromatic number (x) = 2.

if given graph is bipartite and have no edge then chromatic number (x) = 1.

So answer is 2