Boundary values in the four color problem

Authors:
Michael O. Albertson and Herbert S. Wilf

Journal:
Trans. Amer. Math. Soc. **181** (1973), 471-482

MSC:
Primary 05C15

MathSciNet review:
0319794

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
05C15

Retrieve articles in all journals with MSC: 05C15

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9947-1973-0319794-7

Article copyright:
© Copyright 1973
American Mathematical Society