Article in volume
Authors:
Title:
On the 12-representability of induced subgraphs of a grid graph
PDFSource:
Discussiones Mathematicae Graph Theory 42(2) (2022) 383-403
Received: 2019-07-29 , Revised: 2019-11-01 , Accepted: 2019-11-10 , Available online: 2019-12-09 , https://doi.org/10.7151/dmgt.2263
Abstract:
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 com- plete
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
References:
- 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 - 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 - S. Kitaev, Existence of u-representation of graphs, J. Graph Theory 85 (2017) 661–668.
https://doi.org/10.1002/jgt.22097 - 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 - S. Kitaev and V. Lozin, Words and Graphs (Springer, Cham, 2015).
https://doi.org/10.1007/978-3-319-25859-1 - 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 - 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 - H. Zarrabi-Zadeh, Online coloring co-interval graphs, Sci. Iran. Transactions D: Computer Science & Engineering and Electrical Engineering 16 (2009) 1–7.
Close