Approximate graph colouring  with a promised upper bound on maximum independent set In my job the following problem arises:

Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)&lt;=64 is known and |V|/64 is a trivial lower, |V| a trivial upper bound. But are there better proven approximations under this special condition?) 

What if we relax to the fractional chromatic number? And to "good" running times in average cases?
Compute a maximum matching in the complement of the input graph. Every unmatched node must be in a different color class in any coloring. So: if you get at least cn matched edges, then the matching itself gives you a coloring with an upper bound of (1-c)n, and an approximation ratio of 64(1-c). If you don't get at least cn edges, then you get a lower bound of (1 - 2c)n colors and an approximation ratio of 1/(1-2c). Solving the equation 64(1-c) = 1/(1-2c) leads to an approximation ratio slightly larger than 32; see Sasho Nikolov's comment for the precise value.