Lab 3: graph coloring (chapter 5)

In combinatorics, a “graph” is just a fancy name for a collection of dots (vertices) and lines (edges) joining them. In this lab we will explore the coloring of graphs— a huge area of research with numerous real world applications. The main question we will be attacking is: how many ways are there to color a given graph so that no two joined vertices get the same color?

Due dates

A draft will is due on October 21—please bring two copies for peer revisions. The final article is due on Monday, October 28.

Code hints

You can create a graph with vertex set $1,2,\ldots$ by listing the edges. For instance, the following code creates a triangle:

g=Graph([(1,2),(2,3),(3,1)])
plot(g)


There are many graphs built in to sage. Type graphs and then press Tab. For example, you can get the complete graph, cycle graph, line graph, etc.

g=graphs.CompleteGraph(5)
g=graphs.CycleGraph(5)
g=graphs.PathGraph(5)


For any graph you can get its chromatic polynomial, both factored and unfactored, with:

g.chromatic_polynomial()
g.chromatic_polynomial().factor()