×

Functigraphs: an extension of permutation graphs. (English) Zbl 1224.05165

Summary: Let \(G_1\) and \(G_2\) be copies of a graph \(G\), and let \(f\: 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\: u \in V(G_1), v \in V(G_2),v=f(u)\}\). In this paper, we study colourability and planarity of functigraphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: EuDML