About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2018, 12:2, 278-296
Volume 25, No 2, 2018, P. 19-53
UDC 519.174
S. V. Kitaev and A. V. Pyatkin
Word-representable graphs: A survey
Abstract:
Letters $x$ and $y$ alternate in a word $w$ if after deleting all letters but $x$ and $y$ in $w$ we get either a word $xyxy \dots$ or a word $yxyx \dots$ (each of these words can be of odd or even length). A graph $G = (V, E)$ is word-representable if there is a finite word $w$ over an alphabet $V$ such that the letters $x$ and $y$ alternate in $w$ if and only if $xy \in E$. The word-representable graphs include many important graph classes, in particular, circle graphs, 3-colorable graphs and comparability graphs. In this paper we present the full survey of the available results on the theory of word-representable graphs and the most recent achievements in this field.
Tab. 2, illustr. 11, bibliogr. 48.
Keywords: representation of graphs, orientation, word, pattern.
DOI: 10.17377/daio.2018.25.588
Sergey V. Kitaev 1
Artem V. Pyatkin 2,3
1. University of Strathclyde,
Livingstone Tower, 26 Richmond St., Glasgow, G1 1XH, UK
2. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
3. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: sergey.kitaev@cis.strath.ac.uk, artem@math.nsc.ru
Received 11 August 2017
Revised 12 December 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.
