As we all know it is $NPH$ to check whether $G=(V,E)$ is $k$-colorable or not. It is also hard to find the chromatic number of $G$. But I'd like to ask what are some good (or best known) approximation for coloring a general graph?
More formally, I am looking at a graph $G=(V,E)$ for which I do not know the chromatic number. I am trying to find a good coloring of such a graph. What is considered good?
For example, if $d=d(G)$ is the degeneracy of the graph, I can color $G$ in $d+1$ colors in linear time. The degeneracy can be computed in polynomial (linear) time.
I'd like to ask for other (polynomial) coloring algorithms that do not know the chromatic number of the graph (Yet, they are may attempt to approximate it in polynomial time), which (obviously) won't lead to $\chi(G)$ colors, but might lead me to either:
- $f(\chi(G))$-coloring, better if $f$ is linear, but also if not.
- $g(G)$-coloring, where $g$ is a parameter of the graph $G$. Such as: degeneracy, maximal degree, etc. Prefferably better than $d+1$-coloring.
Basically, I have a graph that I only know $V$ and $E$. I don't know $\chi(G)$ or anything else. So anything I want to know must be computed (or approximatex) polynomially.
Now, I want to color this graph in the best possible way that will require polynomial time. Or, in one of the best ways if there are several.
I tried looking online, but could not find such results. There are many negative results, showing some approximations are $NPH$, but I am looking for the positive results.