Suppose we have a graph of 'n' nodes and 'e' edges. Is there any way to find the number of colors needed to color the graph? I know that the upper bound for number of colors is 'n'. But is there a formula to find number of colors needed which is less than 'n' (if possible) that will definitely color the graph? The number may or may not be the chromatic number.
Will having other information such as degree of nodes help?