What little i know is that a discrete graph and an empty graph has chromatic number $1$, while a complete graph with $n$ vertices has a chromatic number $n$. I am curious to know whether there is any known formula to calculate the chromatic number of a simple graph $G$ just by knowing its number of vertices ( order) and number of edges (size)? Any reference (if possible) in this regards would also be appreciated.

  • $\begingroup$ no. consider 4 vertices with 3 edges. one possibility is a triangle and an isolated vertex, which has chromatic number 3. another possibility is a square with 3 out of 4 sides, which has chromatic number 2 $\endgroup$ – mathworker21 Aug 2 at 16:23
  • $\begingroup$ Try Googling "chromatic number" $\endgroup$ – saulspatz Aug 2 at 17:32

The problem of finding the chromatic number of a graph in general in an NP-complete problem.

https://www2.cs.duke.edu/courses/fall05/cps230/L-24.pdf (see the last page)

So there is no general formula to calculate the chromatic number based on the number of vertices and edges. There are a number of types of graphs for which we know the chromatic number (e.g., cycles), and we know a number of bounds on the chromatic number (both upper and lower). But there is no known formula based only on vertices and edges.

  • $\begingroup$ That "so" is very weird. The fact that chromatic number is not merely a function of # of vertices and edges is WAYYYYY easier than proving that finding the chromatic number is an NP-complete problem $\endgroup$ – mathworker21 Aug 3 at 4:31

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.