Functigraphs: An extension of permutation graphs
Andrew Tzer-Yeu Chen, Daniela Ferrero, Ralucca Gera, Eunjeong Yi · Mathematica Bohemica · 2011
Let $G_1$ and $G_2$ be copies of a graph $G$, and let $f\colon V(G_1) \rightarrow V(G_2)$ be a function. Then a functigraph $C(G, f)=(V, E)$ is a generalization of a permutation graph, where $V=V(G_1) \cup V(G_2)$ and $E=E(G_1) \cup E(G_2)\cup \{uv \colon u \in V(G_1), v \in V(G_2),v=f(u)\}$. In this paper, we study colorability and planarity of functigraphs.