Boundary Values in the Four Color Problem
Michael O. Albertson, Herbert S. Wilf · Transactions of the American Mathematical Society · 1973
Let $G$ be a planar graph drawn in the plane so that its outer boundary is a $k$-cycle. A four coloring of the outer boundary $\gamma$ is admissible if there is a four coloring of $G$ which coincides with $\gamma$ on the boundary. If $\psi$ is the number of admissible boundary colorings, we show that the 4CC implies $\psi \geqslant 3 \cdot {2^k}$ for $k = 3, \cdots ,6$. We conjecture this to be true for all $k$ and show $\psi$ is $\geqslant c{((1 + {5^{1/2}})/2)^k}$. A graph is totally reducible (t.r.) if every boundary coloring is admissible. There are triangulations of the interior of a $k$-cycle which are t.r. for anv $k$. We investigate a class of graphs called annuli, characterize t.r. annuli and show that annuli satisfy the above conjecture.