Том 25, номер 2, 2018 г., Стр. 19-53

УДК 519.174
Китаев С. В., Пяткин А. В.
Графы, представимые в виде слов: обзор результатов

Аннотация:
Будем говорить, что буквы $x$ и $y$ чередуются в слове $w$, если при удалении из $w$ всех букв кроме $x$ и $y$ получается либо слово вида $xyxy \dots$ , либо слово вида $yxyx \dots$ (каждое из этих слов может иметь как чётную, так и нечётную длину). Граф $G = (V, E)$ представим в виде слова, если существует конечное слово $w$ над алфавитом $V$ , в котором буквы $x$ и $y$ чередуются тогда и только тогда, когда $xy \in E$.
Графы, представимые в виде слов, включают многие важные классы графов, например: графы пересечения хорд, 3-раскрашиваемые графы и графы сравнимости. В настоящей статье даётся полный обзор известных результатов по теории графов, представимых в виде слов, включая самые последние достижения в этой области.
Табл. 2, ил. 11, библиогр. 48.

Ключевые слова: представление графов, ориентация, слово, паттерн.

DOI: 10.17377/daio.2018.25.588

Китаев Сергей Владимирович ¹
Пяткин Артём Валерьевич ^2,3
1. University of Strathclyde,
Livingstone Tower, 26 Richmond St., Glasgow, G1 1XH, UK
2. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
3. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: sergey.kitaev@cis.strath.ac.uk, artem@math.nsc.ru

Статья поступила 11 августа 2017 г.
Исправленный вариант — 12 декабря 2017 г.

Литература

[1] Akrobotu P., Kitaev S., Masárová Z. On word-representability of polyomino triangulations // Sib. Adv. Math. 2015. Vol. 25, No. 1. P. 1–10.

[2] Babson E., Steingrímsson E. Generalized permutation patterns and a classification of the Mahonian statistics // Sémin. Lothar. Comb. 2000. No. B44b. P. 1–18.

[3] Balogh J., Bollobás B., Weinreich D. A jump to the Bell number for hereditary graph properties // J. Comb. Theory, Ser. B. 2005. Vol. 95. P. 29–48.

[4] Beigel R., Eppstein D. 3-Coloring in time O(1.3289n) // J. Algorithms. 2005. Vol. 54, No. 2. P. 168–204.

[5] Berstel J., Karhumäki J. Combinatorics on words — a tutorial // Bull. Eur. Assoc. Theor. Comput. Sci. 2003. Vol. 79. P. 178–228.

[6] Berstel J., Perrin D. The origins of combinatorics on words // Eur. J. Comb. 2007. Vol. 28, No. 3. P. 996–1022.

[7] Bell E. J. L., Rayson P., Berridge D. The strong-connectivity of word-representable digraphs. 2011. (Cornell Univ. Libr. e-Print Archive; arXiv:1102.0980).

[8] Bomze I. M., Budinich M., Pardalos P. M., Pelillo M. The maximum clique problem // Handbook of Combinatorial Optimization. Suppl. Vol. A. Dordrecht: Kluwer Acad. Publ., 1999. P. 1–74.

[9] Bóna M. Combinatorics of permutations. Boca Raton, FL: Chapman & Hall/CRC, 2004. (Discrete Math. Appl.).

[10] Brightwell G. On the complexity of diagram testing // Order. 1993. Vol. 10, No. 4. P. 297–303.

[11] Brändén P., Claesson A. Mesh patterns and the expansion of permutation statistics as sums of permutation patterns // Electron. J. Comb. 2011. Vol. 18, No. 2, Res. Pap. P5. 14 p.

[12] $\breve{C}$ern$\acute{y}$ J. Coloring circle graphs // Electron. Notes Discrete Math. 2007. Vol. 29. P. 457–461.

[13] Chvátal V., Hammer P. Aggregation of inequalities in integer programming // Studies in integer programming. Amsterdam: North-Holland, 1977. P. 145–162. (Ann. Discrete Math.; Vol. 1).

[14] Chen T. Z. Q., Kitaev S., Sun B. Y. Word-representability of face subdivisions of triangular grid graphs // Graphs Comb. 2016. Vol. 32, No. 5. P. 1749–1761.

[15] Chen T. Z. Q., Kitaev S., Sun B. Y. Word-representability of triangulations of grid-covered cylinder graphs // Discrete Appl. Math. 2016. Vol. 213. P. 60–70.

[16] Claesson A. Generalised pattern avoidance // Eur. J. Comb. 2001. Vol. 22. P. 961–971.

[17] Collins A., Kitaev S., Lozin V. New results on word-representable graphs // Discrete Appl. Math. 2017. Vol. 216. P. 136–141.

[18] Diestel R. Graph theory. 5th ed. Heidelberg: Springer, 2016. (Grad. Texts Math.; Vol. 173).

[19] Fernandes C. G., Green E. L., Mandel A. From monomials to words to graphs // J. Comb. Theory, Ser. A. 2004. Vol. 105, No. 2. P. 185–206.

[20] Garey M. R., Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman, 1979.

[21] Gao A. L. L., Kitaev S., Zhang P. B. On 132-representable graphs // Australas. J. Comb. 2017. Vol. 69, No. 1. P. 105–118.

[22] Glen M. Colourability and word-representability of near-triangulations. 2016. (Cornell Univ. Libr. e-Print Archive; arXiv:1605.01688).

[23] Glen M. The software available at http://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html

[24] Glen M., Kitaev S. Word-representability of triangulations of rectangular polyomino with a single domino tile // J. Comb. Math. Comb. Comput. 2017. Vol. 100. P. 131–144.

[25] Glen M., Kitaev S., Pyatkin A. On the representation number of a crown graph. 2016. (Cornell Univ. Libr. e-Print Archive; arXiv:1609.00674).

[26] Graham R., Zang N. Enumerating split-pair arrangements // J. Comb. Theory, Ser. A. 2008. Vol. 115, No. 2. P. 293–303.

[27] Halldórsson M., Kitaev S., Pyatkin A. Graphs capturing alternations in words // Developments in language theory: Proc. 14th Int. Conf. DLT2010 (London, ON, Canada, Aug. 17–20, 2010). Heidelberg: Springer, 2010. P. 436–437. (Lect. Notes Comp. Sci.; Vol. 6224).

[28] Halldórsson M., Kitaev S., Pyatkin A. Alternation graphs // Graph-Theoretic Concepts in Computer Science: Revis. Pap. 37th Int. Workshop,WG2011 (Teplá Monastery, Czech Republic, June 21–24, 2011). Heidelberg: Springer, 2011. P. 191–202. (Lect. Notes Comp. Sci.; Vol. 6986).

[29] Halldórsson M., Kitaev S., Pyatkin A. Semi-transitive orientations and word-representable graphs // Discrete Appl. Math. 2016. Vol. 201. P. 164–171.

[30] Jones M., Kitaev S., Pyatkin A., Remmel J. Representing graphs via pattern avoiding words // Electron. J. Comb. 2015. Vol. 22, No. 2, Res. Pap. P2.53. 20 p.

[31] Kitaev S. Patterns in permutations and words. Heidelberg: Springer, 2011. (Monogr. Theor. Comp. Sci., EATCS Ser.).

[32] Kitaev S. On graphs with representation number 3 // J. Autom. Lang. Comb. 2013. Vol. 18, No. 2. P. 97–112.

[33] Kitaev S., Lozin V. Words and graphs. Cham: Springer, 2015. (Monogr. Theor. Comp. Sci., EATCS Ser.).

[34] Kitaev S., Pyatkin A. On representable graphs // J. Autom. Lang. Comb. 2008. Vol. 13, No. 1. P. 45–54.

[35] Kitaev S., Salimov P., Severs C., Úlfarsson H. On the representability of line graphs // Developments in language theory: Proc. 15th Int. Conf. DLT2011 (Milan, Italy, July 19–22, 2011). Heidelberg: Springer, 2011. P. 478–479. (Lect. Notes Comp. Sci.; Vol. 6795).

[36] Kitaev S., Seif S. Word problem of the Perkins semigroup via directed acyclic graphs // Order. 2008. Vol. 25, No. 3. P. 177–194.

[37] Koebe M. On a new class of intersection graphs // Ann. Discrete Math. 1992. Vol. 51. P. 141–143.

[38] Korpelainen N., Lozin V. Two forbidden induced subgraphs and well-quasi-ordering // Discrete Math. 2011. Vol. 311, No. 16. P. 1813–1822.

[39] Lovász L. Perfect graphs // Selected topics graph theory. V. 2. London: Acad. Press, 1983. P. 55–87.

[40] Marcus A., Tardos G. Excluded permutation matrices and the Stanley–Wilf conjecture // J. Comb. Theory, Ser. A. 2004. Vol. 107, No. 1. P. 153–160.

[41] Mandelshtam Y. On graphs representable by pattern-avoiding words. 2016. (Cornell Univ. Libr. e-Print Archive; arXiv:1608.07614).

[42] Perkins P. Bases for equational theories of semigroups // J. Algebra. 1969. Vol. 11, No. 2. P. 298–314.

[43] Petkov$\check{s}$ek M. Letter graphs and well-quasi-order by induced subgraphs // Discrete Math. 2002. Vol. 244. P. 375–388.

[44] Pretzel O. On graphs that can be oriented as diagrams of ordered sets // Order. 1985. Vol. 2, No. 1. P. 25–40.

[45] Prüfer H. Neuer Beweis eines Satzes über Permutationen // Arch. Math. Phys. 1918. Vol. 27. P. 742–744.

[46] Steingrímsson E. Generalized permutation patterns – a short survey // Permutation patterns. New York, Camb. Univ. Press, 2010. P. 137–152. (Lond. Math. Soc. Lect. Notes Ser.; Vol. 376).

[47] Thomassen C. A short list color proof of Grötzsch’s theorem // J. Comb. Theory, Ser. B. 2003. Vol. 88, No. 1. P. 189–192.

[48] West D. B. Introduction to graph theory. Upper Saddle River, NJ: Prentice Hall, 1996.