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

Chen, Joanna N. and Kitaev, Sergey (2019) On the 12-representability of induced subgraphs of a grid graph. Discussiones Mathematicae Graph Theory. ISSN 1234-3099 (In Press)

Text (Chen-Kitaev-DMGT-2019-On-the-12-representability-of-induced-subgraphs-of-a-grid-graph)
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 logo

Download (207kB)| Preview


    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.