Graph Chromatic Number Problem Let the integer $1,2,3, \dots, 100$ be the vertices of a graph $G$ and let $i \neq j$ be connected if either $i|j$ or $j|i$. What is the chromatic number of $G$?
I guess the chromatic number would be $7$ since $\{1,2,4,8,16,32,64\}$ forms a clique. But I haven't figured out a proof yet.
 A: I think I just solved the problem myself...Color integer 1 with color 1, 2 with color 2, 4 with color 3,...., 64 with color 7. Then color integer between 2-4 with color 2, integer between 4-8 with color 3,...,integers between 64 to 100 with color 7.That will give a 7-coloring. Since there exists a 7-clique, there cannot be a coloring using less than 7 colors.
A: The greedy algorithm for the vertex ordering 1 < 2 < 3 < ... gives an optimal coloring, that uses the minimum number of colors for every induced subgraph.  
http://en.wikipedia.org/wiki/Perfectly_orderable_graph
http://en.wikipedia.org/wiki/Comparability_graph
This is the same as the coloring in Arthur's answer, by number of prime factors (with multiplicity).
A: Alternate solution: Give vertex $i$ colour number $c$ if there are exactly $c-1$ primes in the prime decomposition of $i$ (counting duplicates). In other words, $1$ gets its own colour, all the primes get one colour, all numbers that are the product of two primes (so $4$, $6$, $9$, $10$ and so on) get colour number $3$, and so on.
Since $i \neq j, i\mid j$ implies that $j$ has more primes in its decomposition than $i$ means that this is a valid colouring. And $64$ and $96$ are the only numbers that need colour number $7$, so we've stayed within the $7$ colours we know we need.
