Communications of the ACM

Last byte

Puzzled: Delightful Graph Theory

By Peter Winkler
Communications of the ACM, August 2008, Vol. 51 No. 8, Page 104
10.1145/1378704.1378726
Comments

1. Since this is an election year, it seems appropriate to visit that impressionable town in which, every evening, each citizen calls all his (or her) friends (always an odd number) and re-chooses his party affiliation—Republican or Democrat—the next day, in accordance with the majority of his friends at the time of the call. Can you show that, after a while, party affiliations will be the same on every alternate day?
2. The island of Foosgangland boasts a complex web of footpaths. Each section of path, from one intersection to the next, is identified by a different number. If you happen to take a walk in Foosgangland, the "length" of your walk is the number of path sections you traverse, and your walk is "increasing" if the path numbers you encounter are always go up. Prove that there is someplace on the island where you can take an increasing walk whose length is at least the average number of paths meeting at the intersections in Foosgangland.
3. In a graph-coloring game, a finite graph G and a palette of k: colors are fixed. Alice and Bob alternately choose an uncolored vertex of G and color it with a color not previously used on any neighboring vertex. Alice, who goes first, wins if all the vertices get colored; but if anyone gets stuck before that happens, Bob wins. (The game is described in an article—Bartnicki, T., Grytczuk, J., Kierstead, H.A., and Zhu, X. The map-coloring game. American Mathematical Monthly 114, 9 (Nov. 2007), 793–803—that pointed out that the following question remains embarrassingly open: Are there a G and a k such that Alice wins on G with k colors, but Bob wins with k+1?)

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.

---

No entries found