Let n 2 be an integer. (a) Show that the graph C2n+1 contains a complete subgraph of

For the graph G of order n = 7 of Figure 14.30, give an example of a k-coloring, using the colors 1, 2, . . . , k, for every integer k with _(G) k n.

For the map M in Figure 14.31, what is the minimum number of colors needed to color the regions of M so that the regions sharing a common boundary are colored differently.

(a) Determine the dual graph G of the map M in Figure 14.32. (b) Determine _(G). (c) What information does _(G) give us about M?

Find a map M whose dual graph is isomorphic the connected planar graph in Figure 14.33.

Determine if the following is a proof of the Four Color Theorem. Proof. Let G be a planar graph. By Kuratowskis theorem, G does not contain K5 as a subgraph. Since _(K5) = 5 and G does not contain K5 as a subgraph, it follows that _(G) 4.

Prove or disprove: If G is a graph with an odd cycle for which there exists a 3-coloring, then _(G) = 3.

Prove or disprove: If G is a graph with an odd cycle for which there exists no 3-coloring, then _(G) = 4.

Determine _(Q3).

Determine the chromatic number of a nontrivial tree.

Determine the chromatic number of the wheel Wn = Cn + K1 for every integer n 3.

Determine the chromatic number of each of the graphs G and H of Figure 14.34.

(a) For the graph G of Figure 14.35, what is the largest complete graph that is a subgraph of G? (b) What does (a) say about _(G)? (c) Determine _(G).

(a) For the graph G of Figure 14.36, what is the largest complete graph that is a subgraph of G? (b) What does (a) say about _(G)? (c) Determine _(G).

Let n 2 be an integer. (a) Show that the graph C2n+1 contains a complete subgraph of order n but no complete subgraph of order n + 1. (b) According to Theorem 14.26, what does the observation in (a) say about _(C2n+1)? (c) Determine _(C2n+1).

Let G be a graph with V (G) = {v1, v2, . . . , vn}. A coloring of the vertices of G is given by the following algorithm. The vertex v1 is assigned the color 1. For an integer k with 1 k < n, once the vertices v1, v2, . . ., vk have been assigned colors, the vertex vk+1 is assigned the smallest color such that vk+1 and any of its neighbors in {v1, v2, . . ., vk} are colored differently. (a) Apply this algorithm to prove Theorem 14.33: For every graph G, _(G) 1 + _(G). (b) Apply this algorithm to the graph G of Figure 14.37. (c) Is it true that this algorithm always gives the chromatic number of a graph?

Eleven cities, denoted by c1, c2, . . . , c11, have applied for admission to a baseball league. The league is to be divided into a certain number of divisions. Two cities cannot belong to the same division if the distance between them is 60 miles or less. A matrix D = [dij ] is given where dij represents the distance between cities ci and cj . What is the smallest number of divisions into which the league can be divided? What is one way of dividing the cities into a smallest number of divisions?

During this coming summer, the Department of Mathematical Sciences at a university plans to offer courses in the following subjects: discrete mathematics (dm), vector calculus (vc), linear algebra (la), data structures (ds), algorithms (al), statistics (st). The following information is known about five students who plan to take courses this summer: Alvin plans to take discrete mathematics, vector calculus and linear algebra. Beverly plans to take discrete mathematics, data structures and linear algebra. Clark plans to take discrete mathematics, algorithms and data structures. Donna plans to take vector calculus and statistics. Edward plans to take statistics and algorithms. The only time periods when courses are taught in the summer are 8:00-9:45, 10:15-12:00, 1:30- 3:15. Can all six courses be offered during these time periods so that two courses are not taught at the same time if some student plans to take both courses?

Seven chemicals c1, c2, . . . , c7 are to be shipped in a number of packages to a university. Because some pairs of chemicals can react with each other, it is not a good idea to ship such pairs of chemicals in the same package. The chemicals that can react with a given chemical are indicated below: c1 : c2, c3, c5, c6 c2 : c1, c3, c4, c5, c6, c7 c3 : c1, c2, c6, c7 c4 : c2, c5, c6, c7 c5 : c1, c2, c4, c6 c6 : c1, c2, c3, c4, c5, c7 c7 : c2, c3, c4, c6 What is the smallest number of packages in which these chemicals can be shipped safely?

Figure 14.38 shows eight traffic lanes L1,L1, . . . ,L8 at the intersection of two streets. A traffic light is located at the intersection. During each phase of the traffic light, those cars in lanes for which the light is green may proceed safely through the intersection into certain permitted lanes. What is the minimum number of phases needed for the traffic light so that all cars may proceed safely through the intersection?

For each possible positive integer k, give an example of a 4-regular graph Gk with _(Gk) = k.

Suppose that G is a graph with chromatic number k 2 and that there is given a k-coloring of G using the colors {1, 2, . . . , k}. Prove or disprove: For every two distinct colors i, j {1, 2, . . . , k}, there are adjacent vertices of G colored i and j.

Show for every two graphs G and H that _(G + H) = _(G) + _(H).

Show for every nontrivial graph G that _(G K2) = _(G).