3 votes 3 votes 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 ? Graph Theory zeal graph-theory discrete-mathematics graph-coloring numerical-answers + – Kabir5454 asked Jan 2, 2023 edited Jan 3, 2023 by Kabir5454 Kabir5454 426 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Aaru_2023 commented Jan 3, 2023 reply Follow Share @Kabir5454 is it 8? 0 votes 0 votes Kabir5454 commented Jan 3, 2023 reply Follow Share yes 0 votes 0 votes Shoto commented Jan 4, 2023 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.