Topological graphs and the Four Color Theorem

$\lambda$-terms can be syntactically represented in different ways than the usual term strings; for example, one can use combinators, string diagrams and for the linear case Zeilberger’s trivalent maps. The main purpose of this paper is to study the relation between arbitrary $\lambda$-terms and maps over orientable surfaces contained in $\mathbb{R}^3$. For this reason, topological graphs are introduced. These graphs include free-edges and hyper-edges to represent, respectively, free and multiple occurrences of variables. Arbitrary $\lambda$-terms without clashes are represented by a subclass of these graphs, called $\omega$-graphs, that include trivalent maps. A translation from $\lambda$-terms into topological graphs is given. The converse of the translation provides a decomposition algorithm that outputs a $\lambda$-term in the class of $\alpha$-equivalent terms associated to each topological graph given as input. This translation provides different names for free-variables. As an application in graph theory, a version of the Four Color Theorem for $\omega$-graphs, which are not necessarily planar, is presented extending in this manner a previous result restricted to a subclass of trivalent maps.