Math 2325
(Chapter 5) - The Coloring of Graphs

Note: Be sure to run the following series of commands first, before anything else!

<<"Combinatorica`";
MyGraph[l_List]:=MakeUndirected[MakeGraph[Union[Flatten[l]],MemberQ[l,{#1,#2}]&]];
ChrPoly[g_]:=Expand[ChromaticPolynomial[g,x]];
ChrPoly[g_,n_]:=ChromaticPolynomial[g,n]

Examples

MyGraph will make an arbitrary graph of your choosing, specified by its edges, expressed as pairs of vertices. To use MyGraph, use the format shown in the following example. We'll use the graph G2 from the book, whose vertices are 1,2, and 3, and whose edges are {1,2} and {2,3}.

GraphG2=MyGraph[{{1,2},{3,2}}];

There are several things to note about this example.  One is that by putting "GraphG2=" at the front, the graph is stored in the variable GraphG2, so we can use it later.  Another is that by putting ";" at the end, we are spared some useless output (try leaving the ";" off, and see what happens!).

Also note that each edge is stored between curly braces, and there is an extra set of curly braces around the whole list of edges.  Finally, it does not matter what order you put the edges in, or even the order you put the vertices within each edge.

To see a graph, use ShowGraph:

ShowGraph[GraphG2]

The Chromatic Polynomial

You can find the chromatic polynomial of a graph as follows:

ChrPoly[GraphG2]

You can also evaluate the chromatic polynomial at different values, which, as discussed in the book, tells you the number of colorings with the given number of colors.  For instance, to see the number of proper colorings of G2with 3 colors, do the following:

ChrPoly[GraphG2,3]

Special Graphs

The Complete Graph

Use CompleteGraph to make the complete graph on a specified number of vertices, the graph where all pairs of vertices form an edge:

ShowGraph[CompleteGraph[4]]

The Path Graph

Use Path to make the path graph on a specified number of vertices, the graph whose edges form a single path from the first vertex to the last vertex:

ShowGraph[Path[4]]

The Cycle Graph

Use Cycle to make the cycle graph on a specified number of vertices, the graph whose edges form a single cycle (a path with an additional edge connecting the first vertex to the last vertex):

ShowGraph[Cycle[4]]

The Graph from Question 4

GraphQ4=MyGraph[{{1,2},{2,3},{3,4},{4,5},{5,6},{6,1},{2,4},{2,5},{1,5}}];

ShowGraph[GraphQ4]

The Graphs from Question 5

Graphs A-C are cycles, and graphs D-F are paths, so you can use the Cycle and Path commands to make those graphs.

Graph G

GraphQ5GG=MyGraph[{{1,2},{2,3},{3,4},{4,1},{2,4}}];

ShowGraph[GraphQ5GG]

Graph H

GraphQ5HH=MyGraph[{{1,2},{2,3},{3,4},{4,5},{5,6},{6,1},{1,4},{2,5},{3,6}}];

ShowGraph[GraphQ5HH]

Graph I

GraphQ5II=MyGraph[{{6,1},{6,2},{6,3},{6,4},{6,5}}];

ShowGraph[GraphQ5II]

Graph J

GraphQ5JJ=MyGraph[{{1,4},{1,6},{2,3},{2,4},{2,5},{2,7},{3,5},{3,7},{4,6},{5,6},{5,7}}];

ShowGraph[GraphQ5JJ]

Graph K

GraphQ5KK=MyGraph[{{1,5},{1,7}, {2,5},{3,4},{3,6},{3,7},{4,6},{5,6},{5,8},{6,7}}];

ShowGraph[GraphQ5KK]

Using special graphs

You can use these special graphs just like other graphs.  For instance, you can find the chromatic polynomials as follows:

ChrPoly[CompleteGraph[3]]

ChrPoly[Path[3]]

ChrPoly[Cycle[3]]

ChrPoly[GraphQ5KK]

Tools for Polynomials

You can use Factor and Simplify on chromatic polynomials (or, indeed on any polynomial).  Factor will factor a polynomial, and Simplify will use Mathematica's best judgement to "simplify" the polynomial (your judgement may differ from Mathematica's).  You can also use Expand on any polynomial (note that the ChrPoly command always produces an "expanded" polynomial).

Factor[ChrPoly[GraphQ5KK]]

Simplify[ChrPoly[GraphQ5JJ]]

Expand[(x-1)^2]

Art Duval, artduval@math.utep.edu
April 4, 2005.
Modified for Mathematica6
November 4, 2008.