0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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). $\endgroup$ – Morgan Rodgers Feb 19 '18 at 5:47
  • $\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$ – user2147710 Feb 19 '18 at 5:58
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Good. Let me encourage you to use those sources to write up and post an answer to your question. $\endgroup$ – Gerry Myerson Feb 19 '18 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$ – Gerry Myerson Feb 20 '18 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.