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)<=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?