Boundary values in the four color problem
Michael O. Albertson and Herbert S. Wilf
Trans. Amer. Math. Soc. 181 (1973), 471-482
Full-text PDF Free Access
Similar Articles |
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.
D. Birkhoff and D.
C. Lewis, Chromatic polynomials, Trans. Amer. Math. Soc. 60 (1946), 355–451. MR 0018401
B. Kempe, On the Geographical Problem of the Four Colours,
Amer. J. Math. 2 (1879), no. 3, 193–200. MR
T. Tutte, On chromatic polynomials and the golden ratio, J.
Combinatorial Theory 9 (1970), 289–296. MR 0272676
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
Retrieve articles in all journals
© Copyright 1973
American Mathematical Society