How do you find the chromatic number?

Answer 1

There are many ways to find the chromatic number. One way is to write the chromatic polynomial and obtain it from that. For example, let's look at a complete graph on 3 points which looks like a triangle. We can color the first vertex in x ways, the second is x-1 ways and the third in x-2 ways. So the chromatic polynomial is C(x)=x(x-1)(x-2) not the smallest natural number, N, such that C(N) is not equal to zero is the chromatic number. So in this case it is 3. This number tells us the we can color the graph with 3 different colors and have no vertices with the same color. Any smaller number of colors, say 2 would not work.


So the answer is find C(x) the chromatic polynomial and then find the smallest natural number such that C(x) is not zero. There are many other methods to find it, but that one is sometimes the simplest.