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.
