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

• I think this is an excellent question for this site; let's hope that someone has a good answer. – Jukka Suomela Oct 19 '11 at 13:57
• @TysonWilliams: I think the question is perfectly clear. Forget the comment, re-read the question. :) – Jukka Suomela Oct 19 '11 at 14:13
• The funny thing is, this conditions guarantees that the trivial approximation is a 64-approximation to the optimum. I wonder whether just the promise of a small independence number can give a better algorithm. – Sasho Nikolov Oct 19 '11 at 16:04
• Is the problem motivated by practical application? If so, one should focus on interesting heuristics that are going to do well - improving the trivial 64 approximation is not that interesting. – Chandra Chekuri Oct 19 '11 at 17:16
• By the way, if you want to find good approximations of the fractional chromatic number quickly, it is sufficient to find good approximations of max-weight independent sets quickly. Hence this suggest a new question: If we know that the largest independent set has size 64, is there an algorithm that finds good approximations of max-weight independent sets much faster than the trivial $O(n^{64})$-time algorithm? – Jukka Suomela Oct 21 '11 at 12:08

• small correcion: in the first case the upper bound is (1-c)n and the lower bound is n/64, so the approx ratio is (1-c)64. When you solve (1-c)64 = 1/(1-2c), you get $c = 3/16 (4-\sqrt{2}) \approx 0.5$ and approximation ratio $\approx 32$. Seems like given an upper bound of $k$ for $\alpha(G)$, this method gives an approximation ratio that goes to $\frac{k}{2}$ as $k$ goes to infinity. – Sasho Nikolov Oct 19 '11 at 17:01
You might be interested in the colouring number, which is 1 plus the maximum over all subgraphs $H$, of the minimum degree of $H$. It can be computed efficiently, and is an upper bound for the chromatic number.