Geodesic
Word-representable graphs: a~survey
Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 19-53.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, word, pattern.
Mots-clés : orientation 
@article{DA_2018_25_2_a1,
     author = {s. V. Kitaev and A. V. Pyatkin},
     title = {Word-representable graphs: a~survey},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {19--53},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2018_25_2_a1/}
}
TY  - JOUR
AU  - s. V. Kitaev
AU  - A. V. Pyatkin
TI  - Word-representable graphs: a~survey
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2018
SP  - 19
EP  - 53
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2018_25_2_a1/
LA  - ru
ID  - DA_2018_25_2_a1
ER  - 
%0 Journal Article
%A s. V. Kitaev
%A A. V. Pyatkin
%T Word-representable graphs: a~survey
%J Diskretnyj analiz i issledovanie operacij
%D 2018
%P 19-53
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2018_25_2_a1/
%G ru
%F DA_2018_25_2_a1
s. V. Kitaev; A. V. Pyatkin. Word-representable graphs: a~survey. Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 19-53. http://geodesic.mathdoc.fr/item/DA_2018_25_2_a1/

[1] Akrobotu P., Kitaev S., Masárová Z., “On word-representability of polyomino triangulations”, Sib. Adv. Math., 25:1 (2015), 1–10 | DOI | MR | Zbl

[2] Babson E., Steingrímsson E., “Generalized permutation patterns and a classification of the Mahonian statistics”, Sémin. Lothar. Comb., B44b (2000), 1–18 | MR

[3] Balogh J., Bollobás B., Weinreich D., “A jump to the Bell number for hereditary graph properties”, J. Comb. Theory Ser. B, 95 (2005), 29–48 | DOI | MR | Zbl

[4] Beigel R., Eppstein D., “$3$-Coloring in time $O(1.3289^n)$”, J. Algorithms, 54:2 (2005), 168–204 | DOI | MR | Zbl

[5] Berstel J., Karhumäki J., “Combinatorics on words – a tutorial”, Bull. Eur. Assoc. Theor. Comput. Sci., 79 (2003), 178–228. | MR | Zbl

[6] Berstel J., Perrin D., “The origins of combinatorics on words”, Eur. J. Comb., 28:3 (2007), 996–1022 | DOI | MR | Zbl

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

[8] Bomze I. M., Budinich M., Pardalos P. M., Pelillo M., “The maximum clique problem”, Handbook of Combinatorial Optimization, Suppl. A, Kluwer Acad. Publ., Dordrecht, 1999, 1–74 | MR | Zbl

[9] Bóna M., Combinatorics of permutations, Discrete Math. Appl., Chapman Hall/CRC, Boca Raton, FL, 2004 | MR | Zbl

[10] Brightwell G., “On the complexity of diagram testing”, Order, 10:4 (1993), 297–303 | DOI | MR | Zbl

[11] Brändén P., Claesson A., “Mesh patterns and the expansion of permutation statistics as sums of permutation patterns”, Electron. J. Comb., 18:2 (2011), Res. Pap. P5, 14 pp. | MR

[12] C̆erný J., “Coloring circle graphs”, Electron. Notes Discrete Math., 29 (2007), 457–461 | DOI | Zbl

[13] Chvátal V., Hammer P., “Aggregation of inequalities in integer programming”, Studies in integer programming, Ann. Discrete Math., 1, North-Holland, Amsterdam, 1977, 145–162 | DOI | MR

[14] Chen T. Z. Q., Kitaev S., Sun B. Y., “Word-representability of face subdivisions of triangular grid graphs”, Graphs Comb., 32:5 (2016), 1749–1761 | DOI | MR | Zbl

[15] Chen T. Z. Q., Kitaev S., Sun B. Y., “Word-representability of triangulations of grid-covered cylinder graphs”, Discrete Appl. Math., 213 (2016), 60–70 | DOI | MR | Zbl

[16] Claesson A., “Generalised pattern avoidance”, Eur. J. Comb., 22 (2001), 961–971 | DOI | MR | Zbl

[17] Collins A., Kitaev S., Lozin V., “New results on word-representable graphs”, Discrete Appl. Math., 216 (2017), 136–141 | DOI | MR | Zbl

[18] Diestel R., Graph theory, Grad. Texts Math., 173, 5th ed., Springer, Heidelberg, 2016 | MR

[19] Fernandes C. G., Green E. L., Mandel A., “From monomials to words to graphs”, J. Comb. Theory Ser. A, 105:2 (2004), 185–206 | DOI | MR | Zbl

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

[21] Gao A. L. L., Kitaev S., Zhang P. B., “On 132-representable graphs”, Australas. J. Comb., 69:1 (2017), 105–118 | MR | Zbl

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

[23] Glen M., The software, Available at , (accessed Feb. 5, 2017) 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., 100 (2017), 131–144 | MR

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

[26] Graham R., Zang N., “Enumerating split-pair arrangements”, J. Comb. Theory Ser. A, 115:2 (2008), 293–303 | DOI | MR | Zbl

[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), Lect. Notes Comp. Sci., 6224, Springer, Heidelberg, 2010, 436–437 | DOI | MR | Zbl

[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), Lect. Notes Comp. Sci., 6986, Springer, Heidelberg, 2011, 191–202 | DOI | MR | Zbl

[29] Halldórsson M., Kitaev S., Pyatkin A., “Semi-transitive orientations and word-representable graphs”, Discrete Appl. Math., 201 (2016), 164–171 | DOI | MR | Zbl

[30] Jones M., Kitaev S., Pyatkin A., Remmel J., “Representing graphs via pattern avoiding words”, Electron. J. Comb., 22:2 (2015), Res. Pap. P2.53, 20 pp. | MR

[31] Kitaev S., Patterns in permutations and words, Monogr. Theor. Comp. Sci., EATCS Ser., Springer, Heidelberg, 2011 | DOI | MR | Zbl

[32] Kitaev S., “On graphs with representation number 3”, J. Autom. Lang. Comb., 18:2 (2013), 97–112 | MR | Zbl

[33] Kitaev S., Lozin V., Words and graphs, Monogr. Theor. Comp. Sci., EATCS Ser., Springer, Cham, 2015 | DOI | MR | Zbl

[34] Kitaev S., Pyatkin A., “On representable graphs”, J. Autom. Lang. Comb. 2008, 13:1, 45–54 | MR | Zbl

[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), Lect. Notes Comp. Sci., 6795, Springer, Heidelberg, 2011, 478–479 | DOI | MR | Zbl

[36] Kitaev S., Seif S., “Word problem of the Perkins semigroup via directed acyclic graphs”, Order, 25:3 (2008), 177–194 | DOI | MR | Zbl

[37] Koebe M., “On a new class of intersection graphs”, Ann. Discrete Math., 51 (1992), 141–143 | DOI | MR | Zbl

[38] Korpelainen N., Lozin V., “Two forbidden induced subgraphs and well-quasi-ordering”, Discrete Math., 311:16 (2011), 1813–1822 | DOI | MR | Zbl

[39] Lovász L., “Perfect graphs”, Selected topics graph theory, v. 2, Acad. Press, London, 1983, 55–87 | MR

[40] Marcus A., Tardos G., “Excluded permutation matrices and the Stanley–Wilf conjecture”, J. Comb. Theory Ser. A, 107:1 (2004), 153–160 | DOI | MR | Zbl

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

[42] Perkins P., “Bases for equational theories of semigroups”, J. Algebra, 11:2 (1969), 298–314 | DOI | MR | Zbl

[43] Petkovšek M., “Letter graphs and well-quasi-order by induced subgraphs”, Discrete Math., 244 (2002), 375–388 | DOI | MR | Zbl

[44] Pretzel O., “On graphs that can be oriented as diagrams of ordered sets”, Order, 2:1 (1985), 25–40 | DOI | MR | Zbl

[45] Prüfer H., “Neuer Beweis eines Satzes über Permutationen”, Arch. Math. Phys., 27 (1918), 742–744

[46] Steingrímsson E., “Generalized permutation patterns – a short survey”, Permutation patterns, Lond. Math. Soc. Lect. Notes Ser., 376, Camb. Univ. Press, New York, 2010, 137–152 | MR | Zbl

[47] Thomassen C., “A short list color proof of Grötzsch's theorem”, J. Comb. Theory Ser. B, 88:1 (2003), 189–192 | DOI | MR | Zbl

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