Previous |  Up |  Next


Title: Functigraphs: An extension of permutation graphs (English)
Author: Chen, Andrew
Author: Ferrero, Daniela
Author: Gera, Ralucca
Author: Yi, Eunjeong
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 136
Issue: 1
Year: 2011
Pages: 27-37
Summary lang: English
Category: math
Summary: 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. (English)
Keyword: permutation graph
Keyword: generalized Petersen graph
Keyword: functigraph
MSC: 05C10
MSC: 05C15
idZBL: Zbl 1224.05165
idMR: MR2807706
DOI: 10.21136/MB.2011.141447
Date available: 2011-03-31T11:21:40Z
Last updated: 2020-07-29
Stable URL:
Reference: [1] Chartrand, G., Frechen, J. B.: On the chromatic number of permutation graphs.Proof Tech. Graph Theory, Proc. 2nd Ann Arbor Graph Theory Conf. 1968 21-24 (1969). Zbl 0199.59401, MR 0250934
Reference: [2] Chartrand, G., Harary, F.: Planar permutation graphs.Ann. Inst. Henri. Poincaré, Nouv. Sér., Sect. B 3 433-438 (1967). Zbl 0162.27605, MR 0227041
Reference: [3] Chartrand, G., Zhang, P.: Introduction to Graph Theory.McGraw-Hill, Kalamazoo, MI (2004).
Reference: [4] Hedetniemi, S.: On classes of graphs defined by special cutsets of lines.Many Facets of Graph Theory, Proc. Conf. Western Michigan Univ., Kalamazoo/Mi. 1968, Lect. Notes Math. 110 171-189 (1969). Zbl 0191.54905, MR 0250921, 10.1007/BFb0060115
Reference: [5] Judson, T. W.: Abstract Algebra: theory and applications.Boston, MA: PWS Publishing Company (1994). Zbl 0823.00002


Files Size Format View
MathBohem_136-2011-1_4.pdf 301.6Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo