graph theory

Question

Let  $G=(V,E)$  where $V=\left \{ 1,2,3,4,.....,150\right \}$ and  $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?

Comments

@Kabir5454 is it 8?

---

yes

---

I am not sure if it is correct or not but this is how I tried to solved it,

To maximise the chromatic number we have to find the maximum size of complete graph where every vertex is connected to each other.

Now first take vertex $1$, then take $2$

Now next vertex to which both $1$ and $2$ are connected is $4$

Next vertex to which $1$, $2$ and $4$ are connected is $8$

Similarly we get complete graph with vertices $\{1,2,4,8,16,32,64,128\}$ and this will be the largest complete graph.

And we need $8$ colours to color them.