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?
A draft will is due on October 21—please bring two copies for peer revisions. The final article is due on Monday, October 28.
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.
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: