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?

  • $\begingroup$ 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? $\endgroup$ Commented Feb 19, 2018 at 5:58

1 Answer 1


There are lots of papers on this. See, for example, Soto, Rossi, and Sevaux, Three new upper bounds on the chromatic number, Discrete Applied Mathematics Vol 159, Issue 18, 6 December 2011, pp. 2281-2289, which might be available at https://www.sciencedirect.com/science/article/pii/S0166218X11003039

See also Upper bound for chromatic number related to number of edges

  • $\begingroup$ Good. Let me encourage you to use those sources to write up and post an answer to your question. $\endgroup$ Commented Feb 19, 2018 at 11:29
  • $\begingroup$ If you're not going to post an answer yourself, you might consider "accepting" mine by clicking in the check mark next to it. $\endgroup$ Commented Feb 20, 2018 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .