answersLogoWhite

0


Best Answer

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.

User Avatar

Wiki User

15y ago
This answer is:
User Avatar

Add your answer:

Earn +20 pts
Q: How do you find the chromatic number?
Write your answer...
Submit
Still have questions?
magnify glass
imp
Related questions

What is the United State's chromatic number?

4


Is colour-critical graph always connected?

Yes. If it was disconnected, you could remove an edge from the component with the lower chromatic number. This wouldn't affect the chromatic number of the first component.


Where can you find a chromatic tuner?

You can find a chromatic tuner at a music shop. This can be online or on the high-street or in a mall. Best to be able to go into a shop to compare or base this decision on online reviews.


What is the chromatic number of an n-vertex simple connected graph which does?

2


What is the Chromatic number of a cycle graph?

3 if n is odd 2 if n is even where n is the number of vertices.


Where is the chromatic located?

"Chromatic" is an adjective and is not located anywhere.


What is relationship between weather and weathering?

I find the chromatic scale very interesting on the Clarinet


Does the iPod chromatic have internet?

the nano chromatic doesn't have internet.


When was Chromatic Palette created?

Chromatic Palette was created in 1981.


When did Chromatic Research end?

Chromatic Research ended in 1998.


When was Chromatic Research created?

Chromatic Research was created in 1994.


What are the 12 traditional pitch classes in music?

chromatic