Let the vertices of the graph G be the numbers 1, 2, ..., 100, and two (different) vertices be adjacent if and only if at least one of 2, 3, or 5 is a common divisor of the respective numbers. Determine χ(G), the chromatic number of the graph G.
I tried to solve and got that all even numbers i.e 2,4,6,...,100 form a clique of size 50. And that all prime numbers are isolated so they do not matter in coloring. But I cannot show chromatic number is 50. Any suggestions?