stringtranslate.com

Gráfico representable mediante palabras

En el campo matemático de la teoría de grafos , un grafo representable por palabras es un grafo que puede ser caracterizado por una palabra (o secuencia) cuyas entradas se alternan de una manera prescrita. En particular, si el conjunto de vértices del grafo es V , uno debería poder elegir una palabra w sobre el alfabeto V de modo que las letras a y b se alternen en w si y solo si el par ab es una arista en el grafo. (Las letras a y b se alternan en w si, después de quitar de w todas las letras excepto las copias de a y b , uno obtiene una palabra abab ... o una palabra baba ....) Por ejemplo, el grafo de ciclo etiquetado por a , b , c y d en el sentido de las agujas del reloj es representable por palabras porque puede ser representado por abdacdbc : los pares ab , bc , cd y ad se alternan, pero los pares ac y bd no.

La palabra w es el representante de palabras de G , y se dice que w representa a G. El grafo no representable por palabras más pequeño (por el número de vértices) es el grafo de rueda W 5 , que es el único grafo no representable por palabras con 6 vértices.

La definición de un gráfico representable mediante palabras funciona tanto en casos etiquetados como no etiquetados, ya que cualquier etiquetado de un gráfico es equivalente a cualquier otro etiquetado. Además, la clase de gráficos representables mediante palabras es hereditaria . Los gráficos representables mediante palabras generalizan varias clases importantes de gráficos, como los gráficos circulares , los gráficos de 3 colores y los gráficos de comparabilidad . Varias generalizaciones de la teoría de los gráficos representables mediante palabras permiten la representación de cualquier gráfico.

Historia

Los grafos representables por palabras fueron introducidos por Sergey Kitaev [1] en 2004 basándose en una investigación conjunta con Steven Seif [2] sobre el semigrupo de Perkins , que ha desempeñado un papel importante en la teoría de semigrupos desde 1960. [3] El primer estudio sistemático de grafos representables por palabras se realizó en un artículo de 2008 de Kitaev y Artem Pyatkin, [4] iniciando el desarrollo de la teoría. Uno de los principales contribuyentes al área es Magnús M. Halldórsson. [5] [6] [7] Hasta la fecha, se han escrito más de 35 artículos sobre el tema, y ​​el núcleo del libro [3] de Sergey Kitaev y Vadim Lozin está dedicado a la teoría de grafos representables por palabras. Una forma rápida de familiarizarse con el área es leer uno de los artículos de la encuesta. [8] [9] [10]

Motivación para estudiar los gráficos

Según [3], los gráficos representables por palabras son relevantes para varios campos, lo que motiva el estudio de los gráficos. Estos campos son el álgebra , la teoría de grafos , la informática , la combinatoria en palabras y la programación . Los gráficos representables por palabras son especialmente importantes en la teoría de grafos, ya que generalizan varias clases importantes de grafos, por ejemplo , los gráficos circulares , los gráficos 3-coloreables y los gráficos de comparabilidad .

Primeros resultados

En [4] se demostró que un grafo G es representable mediante palabras si es k-representable para algún k , es decir, G puede representarse mediante una palabra que tenga k copias de cada letra. Además, si un grafo es k -representable, entonces también es ( k  + 1)-representable. Por lo tanto, la noción de número de representación de un grafo , como el k mínimo tal que un grafo es representable mediante palabras, está bien definida. Los grafos no representables mediante palabras tienen el número de representación ∞. Los grafos con número de representación 1 son precisamente el conjunto de grafos completos , mientras que los grafos con número de representación 2 son precisamente la clase de grafos circulares no completos. En particular, los bosques (excepto los árboles individuales en como máximo 2 vértices), los grafos de escalera y los grafos de ciclo tienen número de representación 2. No se conoce ninguna clasificación para los grafos con número de representación 3. Sin embargo, hay ejemplos de tales grafos, por ejemplo, el grafo de Petersen y los prismas. Además, la 3- subdivisión de cualquier grafo es 3-representable. En particular, para cada grafo G existe un grafo 3-representable H que contiene a G como un menor . [4]

Un grafo G es permutacionalmente representable si puede ser representado por una palabra de la forma p 1 p 2 ... p k , donde p i es una permutación . También se puede decir que G es permutacionalmente k -representable . Un grafo es permutacionalmente representable si y solo si es un grafo de comparabilidad . [2] Un grafo es representable por palabras implica que el vecindario de cada vértice es permutacionalmente representable (es decir, es un grafo de comparabilidad ). [2] La inversa de la última afirmación no es cierta. [5] Sin embargo, el hecho de que el vecindario de cada vértice sea un grafo de comparabilidad implica que el problema de la camarilla máxima es polinomialmente solucionable en grafos representables por palabras. [6] [7]

Orientaciones semitransitivas

Las orientaciones semitransitivas proporcionan una herramienta poderosa para estudiar grafos representables por palabras. Un grafo dirigido está orientado semitransitivamente si es acíclico y para cualquier camino dirigido u 1 → u 2 → ...→ u t , t ≥ 2, o bien no hay arista de u 1 a u t o bien existen todas las aristas u i → u j para 1 ≤ i < j ≤ t . Un teorema clave en la teoría de grafos representables por palabras establece que un grafo es representable por palabras si admite una orientación semitransitiva. [7] Como corolario de la prueba del teorema clave se obtiene un límite superior para los representantes de palabras: Cada grafo no completo representable por palabras G es 2( n  −  κ ( G ))-representable, donde κ ( G ) es el tamaño de una camarilla maximal en G . [7] Como corolario inmediato de la última afirmación, se tiene que el problema de reconocimiento de representabilidad de palabras está en NP . En 2014, Vincent Limouzy observó que es un problema NP-completo reconocer si un grafo dado es representable en palabras. [3] [8] Otro corolario importante del teorema clave es que cualquier grafo 3-coloreable es representable en palabras. El último hecho implica que muchos problemas de grafos clásicos son NP-difíciles en grafos representables en palabras.  

Resumen de resultados seleccionados

Gráficos no representables mediante palabras

Los grafos de rueda W 2 n +1 , para n ≥ 2, no son representables por palabras y W 5 es el grafo no representable por palabras mínimo (por el número de vértices). Tomando cualquier grafo no comparable y agregándole un vértice (un vértice conectado a cualquier otro vértice), obtenemos un grafo no representable por palabras, que luego puede producir infinitos grafos no representables por palabras. [3] Cualquier grafo producido de esta manera necesariamente tendrá un triángulo (un ciclo de longitud 3) y un vértice de grado al menos 5. Existen grafos no representables por palabras de grado máximo 4 [11] y existen grafos libres de triángulos no representables por palabras. [6] También existen grafos regulares no representables por palabras. [3] Los grafos conexos no isomorfos no representables por palabras con un máximo de ocho vértices fueron enumerados por primera vez por Heman ZQ Chen. Sus cálculos se ampliaron en [12] , donde se demostró que los números de grafos conexos no isomorfos no representables por palabras en 5−11 vértices están dados, respectivamente, por 0, 1, 25, 929, 54957, 4880093, 650856040. Esta es la secuencia A290814 en la Enciclopedia en línea de secuencias de enteros (OEIS).

Operaciones sobre gráficos y representabilidad de palabras

Las operaciones que preservan la representabilidad de las palabras son la eliminación de un vértice, la sustitución de un vértice por un módulo, el producto cartesiano, el producto raíz, la subdivisión de un grafo, la conexión de dos grafos por una arista y la unión de dos grafos en un vértice. [3] Las operaciones que no preservan necesariamente la representabilidad de las palabras son la toma del complemento, la toma del grafo lineal, la contracción de aristas, [3] la unión de dos grafos en una camarilla de tamaño 2 o más, [13] el producto tensorial, el producto lexicográfico y el producto fuerte. [14] La eliminación de aristas, la adición de aristas y el levantamiento de aristas con respecto a la representabilidad de las palabras (equivalentemente, la orientabilidad semitransitiva) se estudian en. [14]

Gráficos con alto número de representación

Si bien cada grafo no completo representable por palabra G es 2( n  −  κ ( G ))-representable, donde κ ( G ) es el tamaño de una camarilla máxima en G , [7] el número de representación más alto conocido es floor( n /2) dado por grafos de corona con un vértice completamente adyacente. [7] Curiosamente, tales grafos no son los únicos grafos que requieren representaciones largas. [15] Se ha demostrado que los propios grafos de corona requieren representaciones largas (posiblemente las más largas) entre grafos bipartitos. [16]

Complejidad computacional

Las complejidades computacionales conocidas para problemas en gráficos representables mediante palabras se pueden resumir de la siguiente manera: [3] [8]

Representación de grafos planares

Los grafos planares sin triángulos son representables mediante palabras. [7] Una cuasi-triangulación sin K4 es 3-coloreable si y solo si es representable mediante palabras; [17] este resultado generaliza los estudios en. [18] [19] La representabilidad mediante palabras de las subdivisiones de caras de los grafos de cuadrícula triangular se estudia en [20] y la representabilidad mediante palabras de las triangulaciones de los grafos cilíndricos cubiertos por cuadrícula se estudia en. [21]

Representación de gráficos divididos

La representación de palabras de grafos divididos se estudia en [22] [13] . En particular, [22] ofrece una caracterización en términos de subgrafos inducidos prohibidos de grafos divididos representables por palabras en los que los vértices en el conjunto independiente tienen un grado de como máximo 2, o el tamaño de la camarilla es 4, mientras que en [ 13] se da una caracterización computacional de grafos divididos representables por palabras con la camarilla de tamaño 5. Además, en [ 22 ] se dan las condiciones necesarias y suficientes para que una orientación de un grafo dividido sea semitransitiva, mientras que en [13] se muestra que los grafos de umbral son representables por palabras y los grafos divididos se utilizan para mostrar que pegar dos grafos representables por palabras en cualquier camarilla de tamaño al menos 2 puede, o no, dar como resultado un grafo representable por palabras, lo que resolvió un problema abierto de larga data.

Gráficos representables mediante palabras que evitan patrones

Un grafo es p -representable si puede ser representado por una palabra evitando un patrón p . Por ejemplo, los grafos 132-representables son aquellos que pueden ser representados por palabras w 1 w 2 ... w n donde no hay 1 ≤ a < b < c ≤ n tales que w a < w c < w b . En [23] se muestra que cualquier grafo 132-representable es necesariamente un grafo circular , y cualquier árbol y cualquier grafo cíclico , así como cualquier grafo en como máximo 5 vértices, son 132-representables. Se mostró en [24] que no todos los grafos circulares son 132-representables, y que los grafos 123-representables son también una subclase propia de la clase de grafos circulares.

Generalizaciones

Varias generalizaciones [25] [26] [27] de la noción de un grafo representable por palabras se basan en la observación de Jeff Remmel de que los no bordes se definen por ocurrencias del patrón 11 (dos letras iguales consecutivas) en una palabra que representa un grafo, mientras que los bordes se definen por la evitación de este patrón. Por ejemplo, en lugar del patrón 11, se puede utilizar el patrón 112, o el patrón 1212, o cualquier otro patrón binario donde se pueda hacer la suposición de que el alfabeto está ordenado de modo que una letra en una palabra correspondiente a 1 en el patrón sea menor que la correspondiente a 2 en el patrón. Dejando que u sea un patrón binario ordenado obtenemos así la noción de un grafo u - representable. Por lo tanto, los grafos representables por palabras son simplemente la clase de grafos 11-representables. Curiosamente, cualquier grafo puede ser u -representado suponiendo que u tiene una longitud de al menos 3. [28]

Otra forma de generalizar la noción de un grafo representable por palabras, nuevamente sugerida por Remmel, es introducir el "grado de tolerancia" k para las ocurrencias de un patrón p que define aristas/no aristas. Es decir, podemos decir que si hay hasta k ocurrencias de p formadas por las letras a y b , entonces hay una arista entre a y b . Esto da la noción de un grafo k - p -representable, y los grafos k -11-representables se estudian en [29] Nótese que los grafos 0-11-representables son precisamente grafos representables por palabras. Los resultados clave en [29] son ​​que cualquier grafo es 2-11-representable y que los grafos representables por palabras son una subclase apropiada de los grafos 1-11-representables. Si cualquier grafo es o no 1-11-representable es un problema abierto desafiante.

Para otro tipo de generalización relevante, Hans Zantema sugirió la noción de una orientación k -semitransitiva refinando la noción de una orientación semitransitiva. [15] La idea aquí es restringirnos a considerar solo caminos dirigidos de longitud que no exceda k mientras se permiten violaciones de la semitransitividad en caminos más largos.

Problemas abiertos

Los problemas abiertos sobre gráficos representables mediante palabras se pueden encontrar en [3] [8] [9] [10] e incluyen:

Literatura

La lista de publicaciones para estudiar la representación de gráficos mediante palabras contiene, pero no se limita a:

  1. Ö. Akgün, IP Gent, S. Kitaev, H. Zantema. Solución de problemas computacionales en la teoría de grafos representables por palabras. Journal of Integer Sequences 22 (2019), Artículo 19.2.5.
  2. P. Akrobotu, S. Kitaev y Z. Masárová. Sobre la representabilidad de las triangulaciones poliominós en palabras. Siberian Adv. Math. 25 (2015), 1−10.
  3. B. Broere. Gráficos representables en palabras, 2018. Tesis de maestría en la Universidad de Radboud, Nijmegen.
  4. B. Broere y H. Zantema. "El k-cube es k-representable", J. Autom., Lang. y Combin. 24 (2019) 1, 3-12.
  5. JN Chen y S. Kitaev. Sobre la representabilidad en 12 de los subgrafos inducidos de un grafo de cuadrícula, Discussiones Mathematicae Graph Theory, para aparecer
  6. TZQ Chen, S. Kitaev y A. Saito. Representación de gráficos divididos mediante palabras, arXiv:1909.09471
  7. TZQ Chen, S. Kitaev y BY Sun. Representabilidad de palabras de subdivisiones de caras de gráficos de cuadrícula triangular, Graphs and Combin. 32(5) (2016), 1749−1761.
  8. TZQ Chen, S. Kitaev y BY Sun. Representabilidad verbal de triangulaciones de gráficos cilíndricos cubiertos por una cuadrícula, Discr. Appl. Math. 213 (2016), 60−70.
  9. G.-S. Cheon, J. Kim, M. Kim y S. Kitaev. Representabilidad de los grafos de Toeplitz en palabras, Discr. Appl. Math., próxima publicación.
  10. G.-S. Cheon, J. Kim, M. Kim y A. Pyatkin. Sobre gráficos representables desde el nivel K hasta el 11. J. Combin. 10 (2019) 3, 491−513.
  11. I. Choi, J. Kim y M. Kim. Sobre operaciones que preservan la capacidad de orientación semitransitiva de los gráficos, Journal of Combinatorial Optimization 37 (2019) 4, 1351−1366.
  12. A. Collins, S. Kitaev y V. Lozin. Nuevos resultados sobre gráficos representables mediante palabras, Discr. Appl. Math. 216 (2017), 136−141.
  13. A. Daigavane, M. Singh, BK George. 2-palabras uniformes: gráficos cíclicos y un algoritmo para verificar representaciones de palabras específicas de gráficos. arXiv:1806.04673 (2018).
  14. M. Gaetz y C. Ji. Enumeración y extensiones de grafos representables por palabras. Lecture Notes in Computer Science 11682 (2019) 180−192. En R. Mercas, D. Reidenbach (Eds) Combinatoria en palabras. PALABRAS 2019.
  15. M. Gaetz y C. Ji. Enumeración y extensiones de representantes de palabras, arXiv:1909.00019.
  16. M. Gaetz y C. Ji. Enumeración y extensiones de representantes de palabras, Combinatoria de palabras, 180-192, Lecture Notes in Comput. Sci., 11682, Springer, Cham, 2019.
  17. A. Gao, S. Kitaev y P. Zhang. En 132 gráficos representables. Australasia J. Combin. 69 (2017), 105-118.
  18. ME Glen. Colorabilidad y representabilidad de palabras de cuasi-triangulaciones, Matemáticas puras y aplicaciones, 28(1), 2019, 70−76.
  19. ME Glen. Sobre la representabilidad de palabras de triangulaciones poliominó y gráficos de corona, 2019. Tesis doctoral, Universidad de Strathclyde.
  20. ME Glen y S. Kitaev. Representabilidad verbal de triangulaciones de poliominós rectangulares con una sola ficha de dominó, J. Combin.Math. Combin. Comput. 100, 131−144, 2017.
  21. ME Glen, S. Kitaev y A. Pyatkin. Sobre el número de representación de un grafo de corona, Discr. Appl. Math. 244, 2018, 89−93.
  22. MM Halldórsson, S. Kitaev, A. Pyatkin Sobre gráficos representables, orientaciones semitransitivas y números de representación, arXiv:0810.0310 (2008).
  23. MM Halldórsson, S. Kitaev, A. Pyatkin (2010) Gráficos que capturan alternancias en palabras. En: Y. Gao, H. Lu, S. Seki, S. Yu (eds), Developments in Language Theory. DLT 2010. Lecture Notes Comp. Sci. 6224, Springer, 436−437.
  24. MM Halldórsson, S. Kitaev, A. Pyatkin (2011) Gráficos de alternancia. En: P. Kolman, J. Kratochvíl (eds), Graph-Theoretic Concepts in Computer Science. WG 2011. Apuntes de clase Comp. Sci. 6986, Springer, 191−202.
  25. M. Halldórsson, S. Kitaev y A. Pyatkin. Orientaciones semitransitivas y grafos representables por palabras, Discr. Appl. Math. 201 (2016), 164−171.
  26. M. Jones, S. Kitaev, A. Pyatkin y J. Remmel. Representación de gráficos mediante palabras que evitan patrones, Electron. J. Combin. 22 (2), Res. Pap. P2.53, 1−20 (2015).
  27. S. Kitaev. Sobre gráficos con número de representación 3, J. Autom., Lang. y Combin. 18 (2013), 97−112.
  28. S. Kitaev. Una introducción completa a la teoría de grafos representables por palabras. En: É. Charlier, J. Leroy, M. Rigo (eds), Developments in Language Theory. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36−67.
  29. S. Kitaev. Existencia de la representación u de grafos, Journal of Graph Theory 85 (2017) 3, 661−668.
  30. S. Kitaev, Y. Long, J. Ma, H. Wu. Representabilidad de palabras de gráficos divididos, arXiv:1709.09725 (2017).
  31. S. Kitaev y V. Lozin. Palabras y gráficos, Springer, 2015. ISBN  978-3-319-25859-1 .
  32. S. Kitaev y A. Pyatkin. Sobre grafos representables, J. Autom., Lang. y Combin. 13 (2008), 45−54.
  33. S. Kitaev y A. Pyatkin. Gráficos representables mediante palabras: una encuesta, Journal of Applied and Industrial Mathematics 12(2) (2018) 278−296.
  34. S. Kitaev y A. Pyatkin. Sobre la orientabilidad semitransitiva de grafos sin triángulos, arXiv:2003.06204v1.
  35. S. Kitaev y A. Saito. Sobre la orientabilidad semitransitiva de los grafos de Kneser y sus complementos, Discrete Math., próximamente.
  36. S. Kitaev, P. Salimov, C. Severs y H. Úlfarsson (2011) Sobre la representabilidad de los gráficos lineales. En: G. Mauri, A. Leporati (eds), Developments in Language Theory. DLT 2011. Lecture Notes Comp. Sci. 6795, Springer, 478−479.
  37. S. Kitaev y S. Seif. Problema verbal del semigrupo de Perkins mediante grafos acíclicos dirigidos, Order 25 (2008), 177−194.
  38. E. Leloup. Graphes representables por mot. Tesis de Maestría, Universidad de Lieja, 2019
  39. Mandelshtam. Sobre gráficos representables mediante palabras que evitan patrones, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.
  40. С. B. Kitaev, A. B. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. análisis e implementación. опер., 2018, tom 25, 2 de noviembre, 19−53.

Software

Aquí se puede encontrar software para estudiar gráficos representables mediante palabras:

  1. ME Glen. Software para trabajar con gráficos representables mediante palabras, 2017. Disponible en https://personal.cis.strath.ac.uk/sergey.kitaev/word-representable-graphs.html.
  2. H. Zantema. Software REPRNR para calcular el número de representación de un gráfico, 2018. Disponible en https://www.win.tue.nl/~hzantema/reprnr.html.

Referencias

  1. ^ Steingrímsson, Einar (2023). "La historia del grupo combinatorio Gotemburgo-Reykjavík-Strathclyde" (PDF) . Combinatoria enumerativa y aplicaciones . 3 (1): Artículo S1H1. doi :10.54550/ECA2023V3S1H1.
  2. ^ abc S. Kitaev y S. Seif. Problema verbal del semigrupo de Perkins mediante grafos acíclicos dirigidos, Order 25 (2008), 177−194.
  3. ^ abcdefghij S. Kitaev y V. Lozin. Palabras y gráficos, Springer, 2015. ISBN 978-3-319-25859-1 
  4. ^ abc S. Kitaev y A. Pyatkin. Sobre grafos representables, J. Autom., Lang. y Combin. 13 (2008), 45−54.
  5. ^ ab MM Halldórsson, S. Kitaev, A. Pyatkin (2010) Gráficos que capturan alternancias en palabras. En: Y. Gao, H. Lu, S. Seki, S. Yu (eds), Developments in Language Theory. DLT 2010. Apuntes de clase Comp. Sci. 6224, Springer, 436−437.
  6. ^ abc MM Halldórsson, S. Kitaev, A. Pyatkin (2011) Gráficos de alternancia. En: P. Kolman, J. Kratochvíl (eds), Graph-Theoretic Concepts in Computer Science. WG 2011. Apuntes de clase Comp. Sci. 6986, Springer, 191−202.
  7. ^ abcdefg M. Halldórsson, S. Kitaev y A. Pyatkin. Orientaciones semitransitivas y grafos representables por palabras, Discr. Appl. Math. 201 (2016), 164−171.
  8. ^ abcd S. Kitaev. Una introducción completa a la teoría de grafos representables por palabras. En: É. Charlier, J. Leroy, M. Rigo (eds), Developments in Language Theory. DLT 2017. Lecture Notes Comp. Sci. 10396, Springer, 36−67.
  9. ^ ab S. Kitaev y A. Pyatkin. Gráficos representables mediante palabras: una encuesta, Journal of Applied and Industrial Mathematics 12(2) (2018) 278−296.
  10. ^ ab C. B. Kitaev, A. B. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. análisis e implementación. oper., 2018, tom 25, 2 de noviembre, 19-53
  11. ^ A. Collins, S. Kitaev y V. Lozin. Nuevos resultados sobre gráficos representables mediante palabras, Discr. Appl. Math. 216 (2017), 136–141.
  12. ^ Ö. Akgün, IP Gent, S. Kitaev, H. Zantema. Solución de problemas computacionales en la teoría de grafos representables por palabras. Journal of Integer Sequences 22 (2019), Artículo 19.2.5.
  13. ^ abcd TZQ Chen, S. Kitaev y A. Saito. Representación de gráficos divididos mediante palabras, arXiv:1909.09471
  14. ^ ab I. Choi, J. Kim y M. Kim. Sobre operaciones que preservan la capacidad de orientación semitransitiva de los gráficos, Journal of Combinatorial Optimization 37 (2019) 4, 1351−1366.
  15. ^ ab Ö. Akgün, IP Gent, S. Kitaev, H. Zantema. Solución de problemas computacionales en la teoría de grafos representables por palabras. Journal of Integer Sequences 22 (2019), Artículo 19.2.5.
  16. ^ ab M. Glen, S. Kitaev y A. Pyatkin. Sobre el número de representación de un gráfico de corona, Discr. Appl. Math. 244, 2018, 89–93.
  17. ^ ab M. Glen. Colorabilidad y representabilidad de palabras de cuasi-triangulaciones, Matemáticas puras y aplicadas, por aparecer, 2019.
  18. ^ P. Akrobotu, S. Kitaev y Z. Masárová. Sobre la representabilidad de las triangulaciones poliominós en palabras. Siberian Adv. Math. 25 (2015), 1−10.
  19. ^ M. Glen y S. Kitaev. Representabilidad verbal de triangulaciones de poliominós rectangulares con una sola ficha de dominó, J. Combin.Math. Combin. Comput. 100, 131−144, 2017.
  20. ^ TZQ Chen, S. Kitaev y BY Sun. Representabilidad mediante palabras de subdivisiones de caras de gráficos de cuadrícula triangular, Graphs and Combin. 32(5) (2016), 1749−1761.
  21. ^ TZQ Chen, S. Kitaev y BY Sun. Representabilidad de palabras de triangulaciones de gráficos cilíndricos cubiertos por una cuadrícula, Discr. Appl. Math. 213 (2016), 60−70.
  22. ^ abc S. Kitaev, Y. Long, J. Ma, H. Wu. Representabilidad de palabras de gráficos divididos, arXiv:1709.09725 (2017).
  23. ^ A. Gao, S. Kitaev y P. Zhang. En 132 gráficos representables. Australasia J. Combin. 69 (2017), 105-118.
  24. ^ Mandelshtam. Sobre gráficos representables mediante palabras que evitan patrones, Discussiones Mathematicae Graph Theory 39 (2019) 375−389.
  25. ^ M. Jones, S. Kitaev, A. Pyatkin y J. Remmel. Representación de gráficos mediante palabras que evitan patrones, Electron. J. Combin. 22 (2), Res. Pap. P2.53, 1−20 (2015).
  26. ^ M. Gaetz y C. Ji. Enumeración y extensiones de grafos representables por palabras. Lecture Notes in Computer Science 11682 (2019) 180−192. En R. Mercas, D. Reidenbach (Eds) Combinatoria en palabras. PALABRAS 2019.
  27. ^ M. Gaetz y C. Ji. Enumeración y extensiones de representantes de palabras, arXiv:1909.00019.
  28. ^ S. Kitaev. Existencia de la representación u de grafos, Journal of Graph Theory 85 (2017) 3, 661−668.
  29. ^ ab G.-S. Cheon, J. Kim, M. Kim y A. Pyatkin. Sobre gráficos representables desde el nivel k hasta el 11. J. Combin. 10 (2019) 3, 491−513.
  30. ^ S. Kitaev. Sobre gráficos con número de representación 3, J. Autom., Lang. y Combin. 18 (2013), 97−112.