Graph Theory Practice 8: (Art Gallery Theorems, Polygons, and Coloring)

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

1. For the plane graphs below determine the number of "diagonals" that must be added so that all faces except the infinite face are triangles.

a.

b.

c.

2. a. Draw two different triangulations using diagonals for the polygon in 1. c.
Note: This means making all the faces except the infinite face into triangles.

b. Color the vertices of the two triangulations with as few colors as possible.

c. If you call the colors a, b, c, ..... as needed, how often does each of the colors that you used appear?

3. Find the minimum number of colors needed to color the faces of the graphs in 1.

(Note: The rule for face colorings is that two faces that share an edge must get different colors.)

4. Find the minimum number of colors needed to color the vertices of the graphs in 1.

5. What is the minimum number of vertex guards needed for the polygon in 1. c.?

6. List all of the ears for the polygon in 1. c.

7. Draw an infinite family of polygons each of which has only 2 ears.

8. What is the largest number of ears that an n-sided polygon can have?