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.

## Monday, April 19, 2010

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment