Graph classes equivalent to 12-representable graphs

Takaoka, Asahi 

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 3, pp. 1023-1035

Résumé

Jones et al. (2015) introduced the notion of u-representable graphs, where u is a word over {1, 2} different from 22⋯2, as a generalization of word-representable graphs. Kitaev (2016) showed that if u is of length at least 3, then every graph is u-representable. This indicates that there are only two nontrivial classes in the theory of u-representable graphs: 11-representable graphs, which correspond to word-representable graphs, and 12-representable graphs. This study deals with 12-representable graphs. Jones et al. (2015) provided a characterization of 12-representable trees in terms of forbidden induced subgraphs. Chen and Kitaev (2022) presented a forbidden induced subgraph characterization of a subclass of 12-representable grid graphs. This paper shows that a bipartite graph is 12-representable if and only if it is an interval containment bigraph. The equivalence gives us a forbidden induced subgraph characterization of 12-representable bipartite graphs since the list of minimal forbidden induced subgraphs is known for interval containment bigraphs. We then have a forbidden induced subgraph characterization for grid graphs, which solves an open problem of Chen and Kitaev (2022). The study also shows that a graph is 12-representable if and only if it is the complement of a simple-triangle graph. This equivalence indicates that a necessary condition for 12-representability presented by Jones et al. (2015) is also sufficient. Finally, we show from these equivalences that 12-representability can be determined in O(n^2) time for bipartite graphs and in O(n(m̅+n)) time for arbitrary graphs, where n and m̅ are the number of vertices and edges of the complement of the given graph.

Détail

Keywords: 12-representable graphs, forbidden induced subgraphs, interval containment bigraphs, simple-triangle graphs, vertex ordering characterization

Bibliographie

[1] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM, Discrete Mathematics and Applications, 1999). https://doi.org/10.1137/1.9780898719796

[2] J.N. Chen and S. Kitaev, On the 12-representability of induced subgraphs of a grid graph, Discuss. Math. Graph Theory 42 (2022) 383–403. https://doi.org/10.7151/dmgt.2263

[3] D.G. Corneil and P.A. Kamula, Extensions of permutation and interval graphs, in: Proc. 18th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 58 (1987) 267–275.

[4] E.M. Eschen and J.P. Spinrad, An O(n2) algorithm for circular-arc graph recognition, in: Proc. of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1993, V. Ramachandran (Ed(s)), (ACM/SIAM 1993) 128–137.

[5] T. Feder, P. Hell and J. Huang, List homomorphisms and circular arc graphs, Combinatorica 19 (1999) 487–505. https://doi.org/10.1007/s004939970003

[6] L. Feuilloley and M. Habib, Graph classes and forbidden patterns on three vertices, SIAM J. Discrete Math. 35 (2021) 55–90. https://doi.org/10.1137/19M1280399

[7] T. Gallai, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66. https://doi.org/10.1007/BF02020961

[8] M.C. Golumbic and A.N. Trenk, Tolerance Graphs (Cambridge Univ. Press, 2004). https://doi.org/10.1017/CBO9780511542985

[9] J. Huang, Representation characterizations of chordal bipartite graphs, J. Combin. Theory Ser. B 96 (2006) 673–683. https://doi.org/10.1016/j.jctb.2006.01.001

[10] J. Huang, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs, Discrete Appl. Math. 245 (2018) 190–193. https://doi.org/10.1016/j.dam.2017.02.001

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

[12] 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) 36–67. https://doi.org/10.1007/978-3-319-62809-7\_2

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

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

[15] G.B. Mertzios, The recognition of simple-triangle graphs and of linear-interval orders is polynomial, SIAM J. Discrete Math. 29 (2015) 1150–1185. https://doi.org/10.1137/140963108

[16] P.K. Saha, A. Basu, M.K. Sen and D.B. West, Permutation bigraphs and interval containments, Discrete Appl. Math. 175 (2014) 71–78. https://doi.org/10.1016/j.dam.2014.05.020

[17] A.M.S. Shrestha, S. Tayu and S. Ueno, On orthogonal ray graphs, Discrete Appl. Math. 158 (2010) 1650–1659. https://doi.org/10.1016/j.dam.2010.06.002

[18] J.P. Spinrad, Efficient Graph Representations (AMS, 2003). https://doi.org/10.1090/fim/019

[19] A. Takaoka, A vertex ordering characterization of simple-triangle graphs, Discrete Math. 341 (2018) 3281–3287. https://doi.org/10.1016/j.disc.2018.08.009

[20] A. Takaoka, A recognition algorithm for simple-triangle graphs, Discrete Appl. Math. 282 (2020) 196–207. https://doi.org/10.1016/j.dam.2019.11.009

[21] A. Takaoka, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Discrete Appl. Math. 279 (2020) 154–167. https://doi.org/10.1016/j.dam.2019.10.028

[22] A. Takaoka, S. Tayu and S. Ueno, Dominating sets and induced matchings in orthogonal ray graphs, IEICE Trans. Inf. & Syst. E97-D (2014) 3101–3109. https://doi.org/10.1587/transinf.2014EDP7184

[23] W.T. Trotter, Jr. and J.I. Moore, Jr., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math. 16 (1976) 361–381. https://doi.org/10.1016/S0012-365X(76)80011-8