Suppose we have a set of n whole numbers $S = \left\{0,1,2,3,...,n \right\}$ and a graph where the nodes are simply elements of $S$. Let the set of connections $C \subset S\times S$ such that $C = \left\{ (x,y) \in S | HCF(x,y) \neq 1 \right\}$. 0 is taken as being not coprime with everything, while 1 is taken as being coprime with everything, 0 notwithstanding. What is the colorability of this graph?
Why :
I was writing a program to color a graph to make exam schedules, so I ended up writing a test script and fed randomly generated data. Could check it for 10 numbers, would not check it for 100
BTW, script to test your input.
EDIT :
Test data (based on the script) :
0-50 : 25 colorable
0-99 : 50 colorable
0-314 : 158 colorable
0-499 : 250 colorable
0-1000 : 501 colorable
The even numbers in $S$ all need to get different colors, which forces us to use at least $k+1$ colors when $S = \{0, 1, \dots, 2k\}$ or when $S = \{0,1,\dots,2k+1\}$.
If all the even numbers get different colors, we can give each odd number the same color as the preceding even number, and the resulting coloring is proper. So this is the actual chromatic number and not just a lower bound.