# Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time

I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $$n$$ vertices in $$O(n^{c_1})$$ time and $$O(n^{c_2})$$ space, for some constants $$c_1$$ and $$c_2$$. More precisely, the algorithm should find an upper and a lower bound on the chromatic number. The closer the bounds are to the chromatic number, the better.

If it isn't clear, the input to the algorithm is a graph. The exact representation of a graph isn't fixed (that is, I will switch data structures if it makes sense).

I already know about Brooks' theorem, which gives an upper bound in linear time and constant space, but I'm hoping for something stronger.

Related Mathoverflow question: https://mathoverflow.net/questions/33812/lower-bounds-for-chromatic-number-of-a-graph

• Can you summarize the research you've already done? Hopefully you've done a literature search of research papers published on approximation algorithms for the chromatic number? If not, I recommend doing that first and then summarizing what you've found.
– D.W.
Jan 21, 2021 at 20:56
• Wow, I only managed to find a single paper that seems relevant, and it was written all the way back in 1968: doi.org/10.1016/S0021-9800(69)80010-4 Jan 21, 2021 at 21:48
• I encourage you to edit your question to summarize that result and its implication for your question. I also encourage you to do a more thorough literature search. Wikipedia cites a paper that supposedly gives an approximation algorithm for the chromatic number. You should also use Google Scholar to check what more recent papers cite them.
– D.W.
Jan 21, 2021 at 22:19
• I also wonder whether I have misunderstood what you mean by "bounds". Are you looking for the approximation factor of an approximation algorithm with the listed running time bound? Are you looking for something else? If something else, please specify the exact task and clarify what you mean by "tightest possible bound". Since you talk about an algorithm, I presume you mean an algorithm that takes a graph as input and outputs (something), but it would help to be clearer about what you mean.
– D.W.
Jan 21, 2021 at 22:20
• Found a few more relevant papers, but don't have time right now to go through them. Jan 22, 2021 at 1:12

The result of Zuckermann tells you that the chromatic number of an $$n$$-vertex graph cannot be approximated in polynomial time to within $$n^{1-\epsilon}$$, for any $$\epsilon > 0$$ unless P = NP. In other words, the problem is extremely hard to approximate, so you won't find good theoretical algorithms for the problem.