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

  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 21 at 20:56
  • $\begingroup$ 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 $\endgroup$ – user2373145 Jan 21 at 21:48
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 21 at 22:19
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 21 at 22:20
  • $\begingroup$ Found a few more relevant papers, but don't have time right now to go through them. $\endgroup$ – user2373145 Jan 22 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.

However, if you care about a practical solution as you claim, i.e., you just want a solution that is computed in a short amount of time and the result is good, there are many things you can try. First, quite a bit depends on the actual instances you want to compute the chromatic number for - what do you know about their structure? For instance, are they sparse or dense?

There a many approaches to try out here. For starters, I would take some sample - representative as possible - of your instances, and see how far their chromatic number is from their clique number (i.e., the size of a maximum clique). Especially if your graphs are sparse, there are very good heuristics and exact solvers available for computing the clique number that can work even on billion-scale graphs. So that will give you a lower bound. If you want a decent algorithm for testing whether that is optimal, you can try a SAT solver. It's simple to map the graph coloring problem to an instance of SAT, and the solvers are highly practical.

Of course, you can also consider a metaheuristic for the problem, say a genetic algorithm or ant colony optimization. For any of these, you can also exploit the lower bound information given via the clique number or upper bound information given by e.g., the maximum degree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.