| 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:
|
http://hdl.handle.net/10338.dmlcz/141447 |
| . |
| 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 |
| . |
