Article in volume
Authors:
Asahi Takaoka
College of Information and Systems, Muroran Institute of Technology
email: takaoka@jindai.jp
Title:
Graph classes equivalent to 12-representable graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(3) (2024) 1023-1035
Received: 2022-07-17 , Revised: 2022-12-12 , Accepted: 2022-12-12 , Available online: 2023-02-18 , https://doi.org/10.7151/dmgt.2486
Abstract:
Jones et al. (2015) introduced the notion of $u$-representable graphs,
where $u$ is a word over $\{1, 2\}$ different from $22\cdots2$, 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(\bar{m}+n))$ time
for arbitrary graphs, where $n$ and $\bar{m}$ are the number of vertices and
edges of the complement of the given graph.
Keywords:
12-representable graphs, forbidden induced subgraphs, interval containment bigraphs, simple-triangle graphs, vertex ordering characterization
References:
- 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 - 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 - 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.
- E.M. Eschen and J.P. Spinrad, An $O(n^2)$ 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.
- T. Feder, P. Hell and J. Huang, List homomorphisms and circular arc graphs, Combinatorica 19 (1999) 487–505.
https://doi.org/10.1007/s004939970003 - 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 - T. Gallai, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66.
https://doi.org/10.1007/BF02020961 - M.C. Golumbic and A.N. Trenk, Tolerance Graphs (Cambridge Univ. Press, 2004).
https://doi.org/10.1017/CBO9780511542985 - 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 - 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 - 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 - 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 - S. Kitaev, Existence of $u$-representation of graphs, J. Graph Theory 85 (2017) 661–668.
https://doi.org/10.1002/jgt.22097 - S. Kitaev and V. Lozin, Words and Graphs (Springer Cham, 2015).
https://doi.org/10.1007/978-3-319-25859-1 - 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 - 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 - 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 - J.P. Spinrad, Efficient Graph Representations (AMS, 2003).
https://doi.org/10.1090/fim/019 - 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 - 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 - 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 - 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 - 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
Close