Boundary values in the four color problem
Abstract: Let be a planar graph drawn in the plane so that its outer boundary is a -cycle. A four coloring of the outer boundary is admissible if there is a four coloring of which coincides with on the boundary. If is the number of admissible boundary colorings, we show that the 4CC implies for . We conjecture this to be true for all and show is .
A graph is totally reducible (t.r.) if every boundary coloring is admissible. There are triangulations of the interior of a -cycle which are t.r. for anv . We investigate a class of graphs called annuli, characterize t.r. annuli and show that annuli satisfy the above conjecture.
- [G] G. D. Birkhoff and D. C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451. MR 0018401, 10.1090/S0002-9947-1946-0018401-4
- [A] A. B. Kempe, On the Geographical Problem of the Four Colours, Amer. J. Math. 2 (1879), no. 3, 193–200. MR 1505218, 10.2307/2369235
- [W] W. T. Tutte, On chromatic polynomials and the golden ratio, J. Combinatorial Theory 9 (1970), 289–296. MR 0272676
- 1. W. T. Tutte, The golden ratio in the theory of chromatic polynomials, Ann. New York Acad. Sci. 175 (1970), 391–402. MR 0265218
- D. Birkhoff and D. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355-451. MR 8, 284. MR 0018401 (8:284f)
- B. Kempe, On the geographical problem of the four colors, Amer. J. Math. 2 (1879), 193-200. MR 1505218
- T. Tutte, On chromatic polynomials and the golden ratio, J. Combinatorial Theory 9 (1970), 289-296. MR 42 #7557. MR 0272676 (42:7557)
- -, The golden ratio in the theory of chromatic polynomials, Internat. Conf. Combinatorial Math. (1970), Ann. New York Acad. Sci. 175 (1970), 391-402. MR 42 #130. MR 0265218 (42:130)
Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C15
Retrieve articles in all journals with MSC: 05C15