Due in class Tuesday, October 15.
1.6.1 #1(abde), #4
1.6.2 #2 (to compute the clique number ?(G), try looking at degrees. To compute ?(G), first argue that in a proper coloring all of the colors in the left column must be different from all of the colors on the right.)
1.6.3 #2
1.6.4 #1(bcde), #2 (hint: use Theorem 1.49 to narrow down the possible graphs that could have this characteristic polynomial, then check cases)
And one more:
A. Suppose that all of the faces of a polyhedron are triangles. If there are F faces,
compute the number of vertices and edges.
Extra credit:
1.6.1 #1(f)
1.6.2 #6
1.6.4 #3
A. Find a general formula for the chromatic polynomial of Kn – e, where e is any edge.
B. Find (with proof) a graph with ?(G) = 3 whose chromatic number is strictly greater than 3.