On the 12-Representability of Induced Subgraphs of a Grid Graph
The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53]. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that a...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2263 |
| _version_ | 1827880299362516992 |
|---|---|
| author | Chen Joanna N. Kitaev Sergey |
| author_facet | Chen Joanna N. Kitaev Sergey |
| author_sort | Chen Joanna N. |
| collection | DOAJ |
| description | The notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53]. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12- representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question of Jones et al. is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. |
| first_indexed | 2024-03-12T18:19:41Z |
| format | Article |
| id | doaj.art-e73562d6dcfa40bcb1fce1d99c77171e |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:41Z |
| publishDate | 2022-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-e73562d6dcfa40bcb1fce1d99c77171e2023-08-02T08:59:13ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-05-0142238340310.7151/dmgt.2263On the 12-Representability of Induced Subgraphs of a Grid GraphChen Joanna N.0Kitaev Sergey1College of Science, Tianjin University of Technology, Tianjin300384, P.R.ChinaDepartment of Mathematics and Statistics, University of Strathclyde, Glasgow, UKThe notion of a 12-representable graph was introduced by Jones, Kitaev, Pyatkin and Remmel in [Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53]. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12- representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question of Jones et al. is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs.https://doi.org/10.7151/dmgt.2263graph representation12-representable graphgrid graphforbidden subgraphsquare grid graphline grid graph05c7505c62 |
| spellingShingle | Chen Joanna N. Kitaev Sergey On the 12-Representability of Induced Subgraphs of a Grid Graph Discussiones Mathematicae Graph Theory graph representation 12-representable graph grid graph forbidden subgraph square grid graph line grid graph 05c75 05c62 |
| title | On the 12-Representability of Induced Subgraphs of a Grid Graph |
| title_full | On the 12-Representability of Induced Subgraphs of a Grid Graph |
| title_fullStr | On the 12-Representability of Induced Subgraphs of a Grid Graph |
| title_full_unstemmed | On the 12-Representability of Induced Subgraphs of a Grid Graph |
| title_short | On the 12-Representability of Induced Subgraphs of a Grid Graph |
| title_sort | on the 12 representability of induced subgraphs of a grid graph |
| topic | graph representation 12-representable graph grid graph forbidden subgraph square grid graph line grid graph 05c75 05c62 |
| url | https://doi.org/10.7151/dmgt.2263 |
| work_keys_str_mv | AT chenjoannan onthe12representabilityofinducedsubgraphsofagridgraph AT kitaevsergey onthe12representabilityofinducedsubgraphsofagridgraph |