Geodesic
On the 12-Representability of Induced Subgraphs of a Grid Graph
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 383-403

Voir la notice de l'article provenant de la source Library of Science

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. 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.
Keywords: graph representation, 12-representable graph, grid graph, forbidden subgraph, square grid graph, line grid graph 
@article{DMGT_2022_42_2_a4,
     author = {Chen, Joanna N. and Kitaev, Sergey},
     title = {On the {12-Representability} of {Induced} {Subgraphs} of a {Grid} {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {383--403},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a4/}
}
TY  - JOUR
AU  - Chen, Joanna N.
AU  - Kitaev, Sergey
TI  - On the 12-Representability of Induced Subgraphs of a Grid Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 383
EP  - 403
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a4/
LA  - en
ID  - DMGT_2022_42_2_a4
ER  - 
%0 Journal Article
%A Chen, Joanna N.
%A Kitaev, Sergey
%T On the 12-Representability of Induced Subgraphs of a Grid Graph
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 383-403
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a4/
%G en
%F DMGT_2022_42_2_a4
Chen, Joanna N.; Kitaev, Sergey. On the 12-Representability of Induced Subgraphs of a Grid Graph. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 383-403. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a4/