Least number of colors needed to color a graph

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?

• The smallest number of necessary colors is the chromatic number, by definition (assuming you are talking about a proper coloring). There is not a formula, for many graphs it is very difficult to find the chromatic number. You can probably find some better upper bounds based on some of the graph properties (e.g. if the graph is planar, it is 4-colorable). – Morgan Rodgers Feb 19 '18 at 5:47
• The graph is not necessarily planar. Is there any general way to represent the upper bound of colors with just the number of nodes, edges and degree information? – user2147710 Feb 19 '18 at 5:58