On the region $ \pi $ chromatic number of snake graph families

A region $ \pi $ coloring of a plane graph assigns colors to its faces so that two faces sharing an edge receive different colors, and so that two faces with different closed edge-neighborhoods receive different sets of colors on those neighborhoods. The least number of colors that permits such an assignment is the region $ \pi $ chromatic number $ R\pi\chi(G) $. This article determines $ R\pi\chi $ for the linear, alternate, cyclic, and double families of planar snake graphs. The values are obtained from two general theorems rather than from separate arguments for each family. The first treats plane graphs in which every interior face meets the outer face, and the interior faces split into $ n $ mutually nonadjacent groups of $ d $ pairwise adjacent faces, and gives $ R\pi\chi = 1 + \min\{k : \binom{k}{d} \geq n\} $. The second treats annular plane graphs with $ p $ petals and gives $ R\pi\chi = p+2 $. The linear and alternate families are the case $ d = 1 $, where $ R\pi\chi $ equals the number of faces, and hence, $ |E|-|V|+2 $ by Euler's formula. The cyclic families are annular, and the double families are the case $ d = 2 $, where the value is $ 2 + \lceil(\sqrt{8n+1}-1)/2\rceil $ and rises by one as $ n $ passes a triangular number. The article also shows that $ R\pi\chi $ is an invariant of a plane graph and not of the underlying planar graph: A nested drawing of the triangular snake $ TS_7 $ needs four colors, whereas the standard drawing needs eight. For the linear and alternate families, the standard drawing is shown to maximize $ R\pi\chi $ over all embeddings. A linear-time algorithm recognizes both patterns and returns an optimal coloring, the associated decision problem is shown to lie in NP, and $ R\pi\chi $ is bounded below by the chromatic number of the dual graph and above by the number of faces.