Monday, April 19, 2010

Homework #5 correction

There was a slight problem with question #2. Here is the corrected version:

2. a) Using a computer algebra system, show that the graph with edges
{(1,2),(1,4),(1,5),(1,6),(2,3),(2,5),(2,7),(3,4),(3,6),(3,9),(5,6),(6,8),(6,9),(7,8),(8,9)}

is 3-colorable. Use the Grobner basis you find to give an explicit 3-coloring. How many colorings are there?
b) Show that if you add edge (1,3) to the graph, it is still 3-colorable, and that the coloring is now unique up to permutation of the colors.

No comments:

Post a Comment