EN|RU
English version: Journal of Applied and Industrial Mathematics, 2018, 12:2, 278-296 |
![]() |
Volume 25, No 2, 2018, P. 19-53 UDC 519.174
Keywords: representation of graphs, orientation, word, pattern. DOI: 10.17377/daio.2018.25.588 Sergey V. Kitaev 1 Received 11 August 2017 References[1] P. Akrobotu, S. Kitaev, and Z. Masárová, On word-representability of polyomino triangulations, Sib. Adv. Math., 25, No. 1, 1–10, 2015.[2] E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sémin. Lothar. Comb., 44, No. B44b, 1–18, 2000. [3] J. Balogh, B. Bollobás, and D. Weinreich, A jump to the Bell number for hereditary graph properties, J. Comb. Theory, Ser. B, 95, 29–48, 2005. [4] R. Beigel and D. Eppstein, 3-Coloring in time $O$(1.3289$n$), J. Algorithms, 54, No. 2, 168–204, 2005. [5] J. Berstel and J. Karhumäki, Combinatorics on words — A tutorial, Bull. EATCS, 79, 178–228, 2003. [6] J. Berstel and D. Perrin, The origins of combinatorics on words, Eur. J. Comb., 28, No. 3, 996–1022, 2007. [7] E. J. L. Bell, P. Rayson, and D. Berridge, The strong-connectivity of word-representable digraphs, 2011 (Cornell Univ. Libr. e-Print Archive, arXiv:1102.0980). [8] I. M. Bomze, M. Budinich, P. M. Pardalos, and M. Pelillo, The maximum clique problem, in Handbook of Combinatorial Optimization, Suppl. Vol. A, pp. 1–74, Kluwer Acad. Publ., Dordrecht, 1999. [9] M. Bóna, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, FL, 2004. [10] G. Brightwell, On the complexity of diagram testing, Order, 10, No. 4, 297–303, 1993. [11] P. Brändén and A. Claesson, Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Electron. J. Comb., 18, No. 2, P5, 1–14, 2011. [12] J. $\breve{C}$erný, Coloring circle graphs, Electron. Notes Discrete Math., 29, 457–461, 2007. [13] V. Chvátal and P. Hammer, Aggregation of inequalities in integer programming, in Studies in Integer Programming, pp. 145–162, North-Holland, Amsterdam, 1977 (Ann. Discrete Math., Vol. 1). [14] T. Z. Q. Chen, S. Kitaev, and B. Y. Sun, Word-representability of face subdivisions of triangular grid graphs, Graphs Comb., 32, No. 5, 1749–1761, 2016. [15] T. Z. Q. Chen, S. Kitaev, and B. Y. Sun, Word-representability of triangulations of grid-covered cylinder graphs, Discrete Appl. Math., 213, 60–70, 2016. [16] A. Claesson, Generalised pattern avoidance, Eur. J. Comb., 22, 961–971, 2001. [17] A. Collins, S. Kitaev, and V. Lozin, New results on word-representable graphs, Discrete Appl. Math., 216, 136–141, 2017. [18] R. Diestel, Graph Theory, Springer, Heidelberg, 2016 (Grad. Texts Math., Vol. 173). [19] C. G. Fernandes, E. L. Green, and A. Mandel, From monomials to words to graphs, J. Comb. Theory, Ser. A, 105, No. 2, 185–206, 2004. [20] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. [21] A. L. L. Gao, S. Kitaev, and P. B. Zhang, On 132-representable graphs, Australas. J. Comb., 69, No. 1, 105–118, 2017. [22] M. Glen, Colourability and word-representability of near-triangulations, 2016 (Cornell Univ. Libr. e-Print Archive, arXiv:1605.01688). [23] M. Glen, The software available at http://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html (accessed Feb. 5, 2017). [24] M. Glen and S. Kitaev, Word-representability of triangulations of rectangular polyomino with a single domino tile, J. Comb. Math. Comb. Comput., 100, 131–144, 2017. [25] M. Glen, S. Kitaev, and A. Pyatkin, On the representation number of a crown graph, 2016 (Cornell Univ. Libr. e-Print Archive, arXiv:1609.00674). [26] R. Graham and N. Zang, Enumerating split-pair arrangements, J. Comb. Theory, Ser. A, 115, No. 2, [27] M. Halldórsson, S. Kitaev, and A. Pyatkin, Graphs capturing alternations in words, in Developments in Language Theory (Proc. 14th Int. Conf., London, ON, Canada, Aug. 17–20, 2010), pp. 436–437, Springer, Heidelberg, 2010 (Lect. Notes Comp. Sci., Vol. 6224). [28] M. Halldórsson, S. Kitaev, and A. Pyatkin, Alternation graphs. in Graph-Theoretic Concepts in Computer Science (Revis. Pap. 37th Int. Workshop, Teplá Monastery, Czech Republic, June 21–24, 2011), pp. 191–202, Springer, Heidelberg, 2011 (Lect. Notes Comp. Sci., Vol. 6986). [29] M. Halldórsson, S. Kitaev, and A. Pyatkin, Semi-transitive orientations and word-representable graphs, Discrete Appl. Math., 201, 164–171, 2016. [30] M. Jones, S. Kitaev, A. Pyatkin, and J. Remmel, Representing graphs via pattern avoiding words, Electron. J. Comb., 22, No. 2, P2.53, 1–20, 2015. [31] S. Kitaev, Patterns in Permutations and Words, Springer, Heidelberg, 2011. [32] S. Kitaev, On graphs with representation number 3, J. Autom. Lang. Comb., 18, No. 2, 97–112, 2013. [33] S. Kitaev and V. Lozin, Words and Graphs, Springer, Cham, 2015. [34] S. Kitaev and A. Pyatkin, On representable graphs, J. Autom. Lang. Comb., 13, No. 1, 45–54, 2008. [35] S. Kitaev, P. Salimov, C. Severs, and H. Úlfarsson, On the representability of line graphs, in Developments in Language Theory (Proc. 15th Int. Conf., Milan, Italy, July 19–22, 2010), pp. 478–479, Springer, Heidelberg, 2011 (Lect. Notes Comp. Sci., Vol. 6795). [36] S. Kitaev and S. Seif, Word problem of the Perkins semigroup via directed acyclic graphs, Order, 25, No. 3, 177–194, 2008. [37] M. Koebe, On a new class of intersection graphs, Ann. Discrete Math., 51, 141–143, 1992. [38] N. Korpelainen and V. Lozin, Two forbidden induced subgraphs and well-quasi-ordering, Discrete Math., 311, No. 16, 1813–1822, 2011. [39] L. Lovász, Perfect graphs, in Selected Topics in Graph Theory, Vol. 2, pp. 55–87, Acad. Press, London, 1983. [40] A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley–Wilf conjecture, J. Comb. Theory, Ser. A, 107, No. 1, 153–160, 2004. [41] Y. Mandelshtam, On graphs representable by pattern-avoiding words, 2016 (Cornell Univ. Libr. e-Print Archive, arXiv:1608.07614). [42] P. Perkins, Bases for equational theories of semigroups, J. Algebra, 11, No. 2, 298–314, 1969. [43] M. Petkovšek, Letter graphs and well-quasi-order by induced subgraphs, Discrete Math., 244, 375–388, 2002. [44] O. Pretzel, On graphs that can be oriented as diagrams of ordered sets, Order, 2, No. 1, 25–40, 1985. [45] H. Prüfer, Neuer Beweis eines Satzes über Permutationen, Arch. Math. Phys., 27, 742–744, 1918 [German]. [46] E. Steingrímsson, Generalized permutation patterns — A short survey, Permutation Patterns, [47] C. Thomassen, A short list color proof of Grötzsch’s theorem, J. Comb. Theory, Ser. B, 88, No. 1, [48] D. B. West, Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NJ, 1996. |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|