A Couple of Useful Tools for Graph Coloring

This page gives a demonstration of the package GraphColoring that was written for Mathematica as a supplement to the standard package Combinatorica written by Pemmaraju and Skiena.  The package GraphColoring calls on the package Combinatorica.  First, I would like to note that I have made a couple of small code changes to Combinatorica.  The first change was to "ExpandVertexOptions" and adds a circle having radius p=0.03 to the possible vertex types.  This main purpose for this change was to construct graphs which could be colored in classroom exercises.  The second change was to "ScreenColorNames" and rearranges the colors in addition to adding a few more common colors to the list.  Consequently, the output generated by using the package GraphColoring may differ from that which is demonstrated here.

The motivation for creating GraphColoring initially arose out the need to obtain a better upper bound on the chromatic number of a graph than what was obtained by using the built-in function "BrelazColoring."  The function created is called "ColorGraph."  The algorithm used for this function determines the color classes by a maximum degree and a maximum intersection property.  As far back as 1995, a variation of this algorithm was used as an aid to study a conjecture of Dirac that there exist vertex k-critical graphs containing no critical edge for k = 4, 5, 6, ...  The colorings obtained by implementing the earlier version of this algorithm admitted a pattern which led to a partial proof of the conjecture.  See [1] and [2] at the end of this page concerning this conjecture of Dirac.

It appears that the function "ColorGraph," greatly improves the upper bound given by "BrelazColoring."  Of course the obvious disadvantage is that it seems to use more time.  Jason McCarty has determined the complexity of "ColorGraph" to be at most O(n⁴ ).  Another function, "TestColorGraph," gives an elementary comparison of the two algorithms.  Using this function, one can see that the two approximations are close for graphs having relatively small order.  For graphs having large order and/or high edge density, it appears that "ColorGraph" yields a much better approximation.  Additionally, in the cases for which "BrelazColoring" yielded a better approximation, it seemed to be better by at most one, a rather peculiar phenomenon.

Here are some examples of the output generated by the package.

The output for this function is the 2-list whose first element is the upper bound on the chromatic number of the graph in question and whose second coordinate is the vertex partition so obtained.  The second example illustrates the option "ExhibitGraph" if the user would like to display the graph.  The graph below belongs to the family of graphs given in [2].

The graph pictured above is a vertex 7-critical graph and contains no critical edge!  Unfortunately, it does not readily follow from the partition given above.  This is because one component of the algorithm used in GraphColoring chooses a vertex having maximum degree as the first member of a color class.  In the earlier version of the algorithm, the first member of a color class was simply a vertex that was not previously chosen having smallest label.  If this earlier version was implemented, then the partition for the same graph above is would have been

.

It was this particular partition and other ones similar to it that exhibited the pattern that led to a partial proof of the conjecture of Dirac.  Notice that if the bound is sharp, then it is readily apparent the vertex 25 is a critical vertex.

A comparison of the two algorithms is given by the following two examples.  The output is the list whose sole member is the average of the differences of the upper bounds for the chromatic numbers generated by the two algorithms.  The next example shows that the test is run on 25 graphs each having between 40 and 65 vertices and each containing about 75% of its edges.

As above, the option "ExhibitTest" can be used to show the chromatic numbers generated for this function.

In addition to the function "ColorGraph," provided in the package GraphColoring, two other functions are defined.  The first is "IndependentSets."  This function computes all independent sets containing a vertex for each vertex in some subset of the vertex set of a graph.  The next two examples illustrate this function.

All independent sets can  be computed as is demonstrated in the following example.

The last function demonstrated is "IndependenceTrees."  This function was created to obtain a visual picture of what the independent sets might look like.  It is not yet clear whether this function will prove useful but at least it was a fun programming exercise.  The output of this function is a sequence of labeled rooted trees, not necessarily having distinct labels, such that in each tree the vertices of any path in the tree correspond to an independent subset vertices in the original graph.  From such output, the independence number of a graph is readily available as well as maximal independent sets.  Because of the relationship between colorations and independent sets, it is hoped that this function might aid in the study of colorations.  The final examples of this page illustrate this function.

All such rooted trees can be computed as demonstrated in the final example.

In conclusion, it is noted that there exist several graph coloring algorithms.  I do not claim that the graph coloring algorithm demonstrated here is original.  There seem to exist some common features between this and other algorithms.

[1] T. R. Jensen, Dense critical and vertex-critical graphs, Discrete Mathematics 258 (2002) 63-84.

[2] J. J. Lattanzio, A note on a conjecture of Dirac, Discrete Mathematics 258 (2002) 323-330.