How can I apply the algorithm in chromatic number?

embizze | High School Teacher | (Level 2) Educator Emeritus

Posted on

I assume we are talking about the chromatic number of a graph G -- each vertex of the graph is "colored" (numbered, assigned a letter, etc...) such that any connected vertices have a different coloring.

It is known that a graph G requires at most D colors where D is the highest valence of any of the vertices (valence being the number of edges coming into a vertex) unless the graph is complete (all vertices connected to all other vertices) or an odd numbered cycle which require D+1 colors. (The chromatic number of a pentagon is 3 despite the highest valence being 2.)

There are a number of algorithms used to compute the chromatic number. However, none are optimal in the sense of always giving the lowest chromatic number for any graph. The problem of finding the chromatic number is NP-complete .

I do not know which algoritms you have available; here are a few:

(1) Brute force -- try every possible coloring. This guarantees an optimal solution but is impossible to do on larger graphs.

(2) A "greedy" algorithm: start at any vertex and color it. Move to an adjacent vertex and color it. Continue, always using a used color if possible. This algorithm can yield an optimal solution, but can also be very bad.

(3) An alternative "greedy" algorithm: list the vertices in descending valence order. Beginning with the vertex with highest valence, color the vertex, then go to the next vertex on the list and color it and continue, always using a used color if possible.

Example: Draw quadrilateral ABCD with diagonal AC drawn. We know that the maximal chromatic number is 3 (the highest valence is 3 and the graph is neither complete nor an odd cycle.) Using (3) we label A 1, label C 2 (we cannot label it 1 as it is connected to A), label B 3 (we cannot use 1 as it is connected to A nor 2 as it is connected to C) and label D 3, so the chromatic number appears to be 3 (and can be shown to be 3 by brute force since the graph is so small.)

Sources: