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/

[1] S.V. Gervacio, T.A. Rapanut and P.C.F. Ramos, Characterization and construction of permutation graphs, Open J. Discrete Math. 3 (2013) 33–38. https://doi.org/10.4236/ojdm.2013.31007

[2] M. Jones, S. Kitaev, A. Pyatkin and J. Remmel, Representing graphs via pattern avoiding words, Electron. J. Combin. 22 (2015) #P2.53. https://doi.org/10.37236/4946

[3] S. Kitaev, Existence of u-representation of graphs, J. Graph Theory 85 (2017) 661–668. https://doi.org/10.1002/jgt.22097

[4] S. Kitaev, A comprehensive introduction to the theory of word-representable graphs, in: Developments in Language Theory, DLT 2017, Lecture Notes in Comput. Sci. 10396, É. Charlier, J. Leroy and M. Rigo (Ed(s)), (Springer, Cham, 2017). https://doi.org/10.1007/978-3-319-62809-7_2

[5] S. Kitaev and V. Lozin, Words and Graphs (Springer, Cham, 2015). https://doi.org/10.1007/978-3-319-25859-1

[6] E. Lappas, S.D. Nikolopoulos and L. Palios, An O(n)-time algorithm for the paired-domination problem on permutation graphs, in: Combinatorial Algorithms, IWOCA 2009, Lectur Notes in Comput. Sci. 5874, J. Fiala, J. Kratochvíl and M. Miller (Ed(s)), (Springer, Berlin, Heidelberg, 2009). https://doi.org/10.1007/978-3-642-10217-2_36

[7] T. Nonner, Clique clustering yields a PTAS for max-coloring interval graphs, in: Automata, Languages and Programming, ICALP 2011, Lectur Notes in Comput. Sci. 6755, L. Aceto, M. Henzinger and J. Sgall (Ed(s)), (Springer, Berlin, Heidelberg, 2011) 183–194. https://doi.org/10.1007/978-3-642-22006-7_16

[8] H. Zarrabi-Zadeh, Online coloring co-interval graphs, Sci. Iran. Transactions D: Computer Science & Engineering and Electrical Engineering 16 (2009) 1–7.