# Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G

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?

• All even numbers form a clique, as they have $2$ as a common divisor. You will need at least $51$ colors. Jun 9 at 16:29
• HOW? Number of even numbers are 50 not 51 Jun 9 at 16:33
• In addition to the 25 prime numbers, there are 4 other isolated vertices: 1, 49, 77, 91.
– Stef
Jun 9 at 21:33

Hint 1:

Show that the graph is $$50$$-partite.

Hint 2:

Each partite set contains exactly two elements.

Full Solution:

For colors $$c_1,\dotsc,c_{50}$$, assign color $$c_i$$ to numbers $$2i-1$$ and $$2i$$. Note that no two consecutive numbers can have a common divisor other than $$1$$.

• Very smart. Thank you Jun 9 at 17:23