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:


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.


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