Characterization of word-representable graphs using modular decomposition

Articles in Press

Document Type : Original paper

Authors

Department of Mathematics, Indian Institute of Technology Guwahati, India

Abstract

In this work, we characterize the class of word-representable graphs with respect to the modular decomposition. Consequently, we determine the representation number of a word-representable graph in terms of the permutation-representation numbers of the subgraphs induced by modules and the representation number of the associated quotient graph. In this context, we also obtain a complete answer to the open problem posed by Kitaev and Lozin on the word-representability of the lexicographical product of graphs.

Keywords

Main Subjects

References

[1] A. Brandstädt, Structure and linear time recognition of 3-leaf powers, Inf. Process. Lett. 98 (2006), no. 4, 133–138.
https://doi.org/10.1016/j.ipl.2006.01.004
[2] I. Choi, J. Kim, and M. Kim, On operations preserving semi-transitive orientability of graphs, J. Comb. Optim. 37 (2019), no. 4, 1351–1366. https://doi.org/10.1007/s10878-018-0358-7
[3] M. Dom, J. Guo, F. Hüffner, and R. Niedermeier, Error compensation in leaf root problems, Algorithms and Computation (Berlin, Heidelberg) (R. Fleischer and G. Trippen, eds.), Springer Berlin Heidelberg, 2005, pp. 389–401.
[4] T. Gallai, Transitiv orientierbare graphen, Acta Math. Hung. 18 (1967), no. 1-2, 25–66. https://doi.org/10.1007/bf02020961
[5] Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, vol. 57, Elsevier, 2004.
[6] M. Habib and C. Paul, A survey of the algorithmic aspects of modular decomposition, Comput. Sci. Rev. 4 (2010), no. 1, 41–59. https://doi.org/10.1016/j.cosrev.2010.01.001
[7] M.M. Halldórsson, S. Kitaev, and A. Pyatkin, Alternation graphs, Graph-Theoretic Concepts in Computer Science (Berlin, Heidelberg) (P. Kolman and J. Kratochv´ıl, eds.), Springer Berlin Heidelberg, 2011, pp. 191–202”.
[8] S. Kitaev, On graphs with representation number 3, J. Autom. Lang. Comb. 18 (2014), no. 2, 97–112.
[9] S. Kitaev and V. Lozin, Words and Graphs, Springer, 2015.
[10] S. Kitaev and A. Pyatkin, On representable graphs, J. Autom. Lang. Comb. 13 (2008), no. 1, 45–54. https://doi.org/10.25596/jalc-2008-045
[11] S. Kitaev and S. Seif, Word problem of the perkins semigroup via directed acyclic graphs, Order 25 (2008), no. 3, 177–194. https://doi.org/10.1007/s11083-008-9083-7
[12] S. Kitaev and H. Sun, Human-verifiable proofs in the theory of word-representable graphs, RAIRO, Theor. Inform. Appl. 58 (2024), 9. https://doi.org/10.1051/ita/2024004
[13] R.M. McConnell and J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999), no. 1-3, 189–241. https://doi.org/10.1016/S0012-365X(98)00319-7
[14] R.H. Möhring, Algorithmic aspects of comparability graphs and interval graphs, Graphs and Order: The Role of Graphs in the Theory of Ordered Sets and Its Applications (I. Rival, ed.), Springer Netherlands, Dordrecht, 1985, pp. 41–101. https://doi.org/10.1007/978-94-009-5315-4_2
[15] R.H. Möhring and F.J. Radermacher, Substitution decomposition for discrete structures and connections with combinatorial optimization, North-Holland mathematics studies, vol. 95, Elsevier, 1984, pp. 257–355. https://doi.org/10.1016/S0304-0208(08)72966-9
[16] K. Mozhui and K.V. Krishna, On the permutation-representation number of bipartite graphs using neighborhood graphs, arXiv preprint arXiv:2311.13980 (2023).
[17] K. Mozhui and K.V. Krishna, Words for the graphs with permutation-representation number at most three, arXiv preprint arXiv:2307.00301 (2023).
[18] N. Nishimura, P. Ragde, and D.M. Thilikos, On graph powers for leaf-labeled trees, J. Algorithms 42 (2002), no. 1, 69–108.  https://doi.org/10.1006/jagm.2001.1195
[19] W.T. Trotter, Combinatorics and Partially Ordered Sets, Johns Hopkins University Press, 1992.
[20] M. Yannakakis, The complexity of the partial order dimension problem, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 351–358.  https://doi.org/10.1137/0603036
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 12 September 2025

Files

Share

How to cite

Statistics