\input zb-basic
\input zb-ioport
\iteman{io-port 05937775}
\itemau{Bernardi, Olivier; Bousquet-M\'elou, Mireille}
\itemti{Counting colored planar maps: algebraicity results.}
\itemso{J. Comb. Theory, Ser. B 101, No. 5, 315-377 (2011).}
\itemab
Summary: We address the enumeration of properly $q$-colored planar maps, or more precisely, the enumeration of rooted planar maps $M$ weighted by their chromatic polynomial $\chi _{M}(q)$ and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when $q\neq 0,4$ is of the form $2+2\cos(j\pi /m)$, for integers $j$ and $m$. This includes the two integer values $q=2$ and $q=3$. We extend this to planar maps weighted by their Potts polynomial $P_{M}(q,\nu )$, which counts all $q$-colorings (proper or not) by the number of monochromatic edges. We then prove similar results for planar triangulations, thus generalizing some results of Tutte which dealt with their proper $q$-colorings. In statistical physics terms, the problem we study consists in solving the Potts model on random planar lattices. From a technical viewpoint, this means solving non-linear equations with two ``catalytic'' variables. To our knowledge, this is the first time such equations are being solved since Tutte's remarkable solution of properly $q$-colored triangulations.
\itemrv{~}
\itemcc{}
\itemut{enumeration; colored planar maps; Tutte polynomial; algebraic generating functions}
\itemli{doi:10.1016/j.jctb.2011.02.003}
\end