Geodesic
Functigraphs: An extension of permutation graphs
Mathematica Bohemica, Tome 136 (2011) no. 1, pp. 27-37

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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.
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.
DOI : 10.21136/MB.2011.141447
Classification : 05C10, 05C15
Keywords: permutation graph; generalized Petersen graph; functigraph 
Chen, Andrew; Ferrero, Daniela; Gera, Ralucca; Yi, Eunjeong. Functigraphs: An extension of permutation graphs. Mathematica Bohemica, Tome 136 (2011) no. 1, pp. 27-37. doi: 10.21136/MB.2011.141447
@article{10_21136_MB_2011_141447,
     author = {Chen, Andrew and Ferrero, Daniela and Gera, Ralucca and Yi, Eunjeong},
     title = {Functigraphs: {An} extension of permutation graphs},
     journal = {Mathematica Bohemica},
     pages = {27--37},
     year = {2011},
     volume = {136},
     number = {1},
     doi = {10.21136/MB.2011.141447},
     mrnumber = {2807706},
     zbl = {1224.05165},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2011.141447/}
}
TY  - JOUR
AU  - Chen, Andrew
AU  - Ferrero, Daniela
AU  - Gera, Ralucca
AU  - Yi, Eunjeong
TI  - Functigraphs: An extension of permutation graphs
JO  - Mathematica Bohemica
PY  - 2011
SP  - 27
EP  - 37
VL  - 136
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2011.141447/
DO  - 10.21136/MB.2011.141447
LA  - en
ID  - 10_21136_MB_2011_141447
ER  - 
%0 Journal Article
%A Chen, Andrew
%A Ferrero, Daniela
%A Gera, Ralucca
%A Yi, Eunjeong
%T Functigraphs: An extension of permutation graphs
%J Mathematica Bohemica
%D 2011
%P 27-37
%V 136
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2011.141447/
%R 10.21136/MB.2011.141447
%G en
%F 10_21136_MB_2011_141447

[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). | MR | Zbl

[2] Chartrand, G., Harary, F.: Planar permutation graphs. Ann. Inst. Henri. Poincaré, Nouv. Sér., Sect. B 3 433-438 (1967). | MR | Zbl

[3] Chartrand, G., Zhang, P.: Introduction to Graph Theory. McGraw-Hill, Kalamazoo, MI (2004).

[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). | DOI | MR | Zbl

[5] Judson, T. W.: Abstract Algebra: theory and applications. Boston, MA: PWS Publishing Company (1994). | Zbl

Cité par Sources :