### Abstract

Original language | English |
---|---|

Number of pages | 22 |

Journal | Discussiones Mathematicae Graph Theory |

Publication status | Accepted/In press - 1 Nov 2019 |

### Fingerprint

### Keywords

- graph representation
- 12-representable graph
- grid graph
- forbidden subgraph
- square grid graph
- line grid graph

### Cite this

*Discussiones Mathematicae Graph Theory*.

}

*Discussiones Mathematicae Graph Theory*.

**On the 12-representability of induced subgraphs of a grid graph.** / Chen, Joanna N.; Kitaev, Sergey.

Research output: Contribution to journal › Article

TY - JOUR

T1 - On the 12-representability of induced subgraphs of a grid graph

AU - Chen, Joanna N.

AU - Kitaev, Sergey

PY - 2019/11/1

Y1 - 2019/11/1

N2 - The notion of a 12-representable graph was introduced by Jones et al.. 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 in 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. In this paper we answer the question of Jones et al.\ by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.

AB - The notion of a 12-representable graph was introduced by Jones et al.. 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 in 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. In this paper we answer the question of Jones et al.\ by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.

KW - graph representation

KW - 12-representable graph

KW - grid graph

KW - forbidden subgraph

KW - square grid graph

KW - line grid graph

UR - https://www.dmgt.uz.zgora.pl/index.php

UR - https://arxiv.org/abs/1911.00408

M3 - Article

ER -