Let the vertices of a graph $G$ be the integers $1,2,\dots,99$. The number $i \neq j$ are connected if their greatest common divisor is at least $3$. Find the chromatic number of $G$.
I think the answer should be $33$ since there exists a $33$-clique formed by $3,6,9,\dots,99$ and we can give a coloring of $33$ by assigning color $1$ to numbers between $3$-$6$ (excluding $6$), $2$ to numbers between $6$-$9$ (excluding $9$), and so on. But I'm not so sure about this algorithm
So, we color each vertex $i$ by a color $\lceil i/3\rceil$, that is the vertices $1$, $2$, and $3$ have color $1$, the vertices $4$, $5$, and $6$ have color $2$, and so on. It rests to check that we have no monochromatic edges. This is true since if numbers $i$ and $j$ are monochromatic then $|j-i|\le 2$ so $$\operatorname{gcd}(i,j)=\operatorname{gcd}(i,j-i)\le 2,$$ thus the vertices $i$ and $j$ are not adjacent.