Граф, представленный в виде слов - Word-representable graph

В математической области теория графов, а граф, представимый в виде слов это график который может быть охарактеризован словом (или последовательностью), элементы которого чередуются определенным образом. В частности, если множество вершин графа V, нужно уметь выбрать слово ш по алфавиту V такие что буквы а и б чередовать в ш тогда и только тогда, когда пара ab является ребром в графе. (Письма а и б чередовать в ш если после удаления из ш все письма, кроме копий а и б, получается слово Abab... или слово баба....) Например, график цикла помеченный а, б, c и d по часовой стрелке представляет собой слово, потому что может быть представлено abdacdbc: пары ab, до н.э, компакт диск и объявление чередуются, но пары ac и bd не.

Слово ш является гс словообразующий, и один говорит, что ш представляет собой г. Наименьшим (по количеству вершин) графом, не представимым словом, является колесо графа W5, который является единственным графом с шестью вершинами, не представимым в виде слов.

Определение графа, представимого в виде слов, работает как в помеченном, так и в немаркированном случаях, поскольку любая разметка графа эквивалентна любой другой разметке. Кроме того, класс графов, представимых в виде слов, является наследственный. Графы, представленные в виде слов, обобщают несколько важных классов графов, таких как круговые графики, 3-раскрашиваемые графики и графики сопоставимости. Различные обобщения теории графов, представимых в виде слов, допускают представление Любые график.

История

Графы, представимые в виде слов, были введены Сергеем Китаевым в 2004 году на основе совместного исследования со Стивеном Сейфом.[1] на Полугруппа Перкинса, которая играет важную роль в теории полугрупп с 1960 года.[2] Первое систематическое исследование графов, представимых в виде слов, было предпринято в 2008 году в статье Китаева и Артема Пяткина.[3] начало разработки теории. Один из ключевых участников этого направления - Магнус М. Халльдорссон[4][5][6]. На сегодняшний день написано более 35 статей по этой теме, и суть книги[2] Сергея Китаева и Вадима Лозина посвящена теории графов, представимых в виде слов. Быстрый способ познакомиться с местностью - прочитать одну из статей обзора.[7][8][9].

Мотивация к изучению графиков

Согласно с [2], графы, представимые в виде слов, относятся к различным областям, что дает мотивацию для изучения графов. Эти поля алгебра, теория графов, Информатика, комбинаторика слов, и планирование. Графы, представимые в виде слов, особенно важны в теории графов, поскольку они обобщают несколько важных классов графов, например круговые графики, 3-раскрашиваемые графики и графики сопоставимости.

Первые результаты

Это было показано в [3] что график г представима в виде слов, если и только если это k-представимый для некоторых k, это, г можно представить словом, имеющим k копии каждого письма. Более того, если граф k-представим, то он также (k +1) -представительный. Таким образом, понятие число представлений графа, как минимум k такой, что граф представим в виде слов, определен правильно. Графы, не представимые в виде слов, имеют число представлений ∞. Графы с номером представления 1 - это в точности набор полные графики, а графы с номером представления 2 - это в точности класс круг неполные графы. Особенно, леса (кроме одиночных деревья не более чем на 2 вершинах), лестничные диаграммы и графики цикла имеют номер представления 2. Классификация графов с номером представления 3 не известна. Однако есть примеры таких графиков, например График Петерсена и призмы. Кроме того, 3-подразделение любого графа 3-представимо. В частности, для каждого графа г существует 3-представимый граф ЧАС который содержит г как незначительный [3].

График г является пермутационно представимый если его можно представить словом в форме п1п2...пk, где пя это перестановка. Он также может сказать, что г является перестановочно k-представительный. Граф является перестановочно представимым тогда и только тогда, когда он график сопоставимости [1]. Представимость графа в словах означает, что окрестности каждой вершины перестановочно представима (т.е.является график сопоставимости ) [1]. Обратное к последнему утверждению неверно [4]. Однако тот факт, что окрестности каждой вершины есть график сопоставимости означает, что Задача максимальной клики полиномиально разрешима на графах, представимых в виде слов [5] [6].

Полупереходные ориентации

Полутранзитивные ориентации предоставляют мощный инструмент для изучения графов, представимых в виде слов. Ориентированный граф - это полупереходно ориентированный если и только это ациклический и для любого направленного пути ты1→ты2→ ...→тыт, т ≥ 2, либо нет ребра из ты1 к тыт или все края тыя → тыj существуют для 1 ≤ я < j ≤ т. Ключевая теорема в теории графов, представимых в виде слов, утверждает, что граф представим в виде слов тогда и только тогда, когда он допускает полупереходную ориентацию [6]. В качестве следствия к доказательству ключевой теоремы получаем верхнюю границу для словесных репрезентантов: каждый неполный граф, представимый в виде слов, г равно 2 (п − κ(г)) - представимая, где κ(г) - размер максимальной клики в г [6]. Непосредственным следствием последнего утверждения является то, что проблема распознавания словесности в НП. В 2014, Винсент Лимузи заметил, что это NP-полная задача распознавать, является ли данный граф представимым в виде слов [2] [7]. Еще одно важное следствие ключевой теоремы состоит в том, что любое 3-цветный граф представима словом. Последний факт означает, что многие классические задачи о графах NP-трудны на графах, представимых в виде слов.

Обзор выбранных результатов

Графы, не представимые в виде слов

Колесные графики W2п+1, для п ≥ 2, не представимы в словах и W5 - минимальный (по количеству вершин) граф, не представимый в виде слов. Беря любой граф несравнимости и добавляя вершину (вершину, соединенную с любой другой вершиной), мы получаем граф, не представимый словом, который затем может создавать бесконечно много графов, не представимых словом [2]. Любой граф, созданный таким образом, обязательно будет иметь треугольник (цикл длины 3) и вершину степени не менее 5. Существуют графы максимальной степени 4, не представимые в виде слов. [10] и не представимые в словах графы без треугольников существуют [5]. Также существуют регулярные графы, не представимые в словах [2]. Неизоморфные связные графы, не представимые в виде слов, содержащие не более восьми вершин, были впервые перечислены Хеманом Z.Q. Чен. Его расчеты были расширены в [11], где было показано, что номера неизоморфных непредставимых связных графов на 5-11 вершинах задаются соответственно числами 0, 1, 25, 929, 54957, 4880093, 650856040. Это последовательность A290814 в то Интернет-энциклопедия целочисленных последовательностей (OEIS).

Операции над графами и представимость слов

Операции, сохраняющие представимость в виде слов, - это удаление вершины, замена вершины модулем, декартово произведение, корневое произведение, подразделение графа, соединение двух графов ребром и склейка двух графов в вершине. [2]. Операции, не обязательно сохраняющие представимость в виде слов, - это взятие дополнения, взятие линейного графа, сжатие ребер. [2], склеивая два графа в клику размером 2 или более [12], тензорное произведение, лексикографическое произведение и сильное произведение [13]. Удаление ребер, добавление ребер и поднятие ребер относительно представимости в виде слов (эквивалентно полупереходной ориентируемости) изучаются в [13].

Графики с большим числом представлений

В то время как каждый неполный граф, представимый в виде слов г равно 2 (п − κ(г)) - представимая, где κ(г) - размер максимальной клики в г [6], наибольшее известное число представлений - этаж (п/ 2) дано корона графики со всем смежной вершиной [6]. Интересно, что такие графы - не единственные графы, требующие длинных представлений. [14]. Показано, что сами графы короны требуют длинных (возможно, самых длинных) представлений среди двудольных графов. [15].

Вычислительная сложность

Известные вычислительные сложности для задач на графах, представимых в виде слов, можно резюмировать следующим образом [2] [7]:

ПРОБЛЕМАСЛОЖНОСТЬ
определение представимости словНП-полный
Доминирующий наборNP-жесткий
Покрытие кликиNP-жесткий
Максимальный независимый наборNP-жесткий
Максимальная кликав P
аппроксимация числа графического представления с точностью до множителя п1−ε для любого ε > 0NP-жесткий

Представление планарных графов

Без треугольников планарные графы представляют собой слова [6]. Почти триангуляция без K4 является 3-раскрашиваемой тогда и только тогда, когда она представима в виде слов. [16]; этот результат обобщает исследования в [17][18]. Представимость граней треугольных сеточных графов изучается в [19] а представимость триангуляций цилиндрических графов с сеткой изучается в [20].

Представление разбитых графов

Словесное представление разделить графики изучается в [21][12]. Особенно, [21] предлагает характеристику в терминах запрещенных индуцированных подграфов представимых в виде слов разделенных графов, в которых вершины в независимом множестве имеют степень не выше 2 или размер клики равен 4, в то время как вычислительная характеристика представимых в виде слов разделенных графов с помощью клика размера 5 приведена в [12]. Кроме того, необходимые и достаточные условия полупереходности ориентации расщепленного графа приведены в [21], пока в [12] пороговые графики показаны как представимые в виде слов, а разбитые графы используются, чтобы показать, что склейка двух графов, представимых в виде слов, в любой клике размером не менее 2 может или не может привести к графу, представимому в виде слов, что решило давнюю открытую проблема.

Графики, представленные по шаблону без слов

График п-представительный если его можно представить словом, избегая шаблон п. Например, 132-представимые графы - это те, которые могут быть представлены словами ш1ш2...шп где нет 1 ≤ а < б < c ≤ п такой, что ша < шc < шб. В [22] показано, что любой 132-представимый граф обязательно является круговой график, и любые дерево и любой график цикла, как и любой граф, содержащий не более 5 вершин, 132-представимы. Это было показано в [23] что не все круговые графы 132-представимы, и что 123-представимые графы также являются собственным подклассом класса круговых графов.

Обобщения

Ряд обобщений [24][25][26] понятия графа, представимого в виде слов, основаны на наблюдении Джефф Реммель что не ребра определяются вхождениями шаблона 11 (две последовательные одинаковые буквы) в слове, представляющем граф, в то время как ребра определяются путем исключения этого шаблона. Например, вместо шаблона 11 можно использовать шаблон 112, или шаблон, 1212, или любой другой двоичный шаблон, в котором предположение, что алфавит упорядочен, можно сделать так, чтобы буква в слове соответствовала 1 в шаблон меньше, чем соответствующий 2 в шаблоне. Сдача ты быть упорядоченным двоичным шаблоном, таким образом, мы получаем понятие ты-представимый график. Итак, графы, представимые в виде слов, - это всего лишь класс 11-представимых графов. Интересно, что любой график может быть ты-представлен при условии ты имеет длину не менее 3 [27].

Другой способ обобщить понятие графа, представимого в виде слов, снова предложен Джефф Реммель, состоит в том, чтобы ввести "степень толерантности" k для вхождений шаблона п определение ребер / не ребер. То есть мы можем сказать, что если есть до k появление п образованный буквами а и б, то между а и б. Это дает понятие k-п-представимый граф, и k-11-представимые графы изучаются в [28]. Обратите внимание, что 0-11-представимые графы - это в точности графы, представимые в виде слов. Ключевые результаты в [28] это что Любые Граф является 2-11-представимым и что графы, представимые словом, являются надлежащим подклассом 1-11-представимых графов. Является ли какой-либо граф 1-11-представимым или нет, - сложная открытая проблема.

Еще одно важное обобщение: Ханс Зантема предложил понятие k-полупереходная ориентация уточнение понятия полупереходной ориентации [14]. Идея здесь ограничивается рассмотрением только направленные дорожки длиной не более k допуская нарушения полупереходности на более длинных путях.

Открытые проблемы

Открытые задачи о графах, представимых в виде слов, можно найти в [2] [7] [8] [9], и они включают:

  • Охарактеризовать (не) представимые в виде слов плоские графы.
  • Охарактеризовать представимые в виде слов почти триангуляции, содержащие полный граф K4 (такая характеристика известна K4-свободные плоские графы [16]).
  • Классифицируйте графы с номером представления 3. (См. [29] за последние достижения в этом направлении.)
  • Это линейный график графа, не представимого в виде слова, всегда не представима словом?
  • Есть ли графики на п вершины, для представления которых требуется больше, чем пол (п/ 2) копии каждого письма?
  • Правда ли, что из всех двудольные графы графы короны требуются самые длинные слово-представители? (Увидеть [15] для соответствующего обсуждения.)
  • Охарактеризуйте графы, представимые в виде слов, в терминах (индуцированных) запрещенных подграфов.
  • Какие (сложные) задачи на графах можно перевести в слова, представляющие их, и решить на словах (эффективно)?

Литература

Список публикаций по изучению представления графов словами содержит, но не ограничивается

  1. Ö. Акгюн, И. Гент, С. Китаев, Х. Зантема. Решение вычислительных задач теории графов, представимых в виде слов. Журнал целочисленных последовательностей 22 (2019), статья 19.2.5.
  2. П. Акроботу, С. Китаев, З. Масарова. О представимости полимино триангуляций в виде слов. Сибирский Adv. Математика. 25 (2015), 1-10.
  3. Б. Броэр. Графы, представимые в виде слов, 2018. Магистерская работа в университете Радбауд, Неймеген.
  4. Б. Броэр и Х. Зантема. "The k-куб k-представляемый, J. Autom., Lang., and Combin. 24 (2019) 1, 3-12.
  5. Дж. Н. Чен и С. Китаев. О 12-представимости индуцированных подграфов сеточного графа, появится Discussiones Mathematicae Graph Theory
  6. Т. З. К. Чен, С. Китаев, А. Сайто. Представление разбитых графов словами, arXiv: 1909.09471
  7. Т. З. К. Чен, С. Китаев, Б. Ю. Сун. Словесная представимость подразделов граней треугольных сеточных графов, Graphs и Combin. 32 (5) (2016), 1749−1761.
  8. Т. З. К. Чен, С. Китаев, Б. Ю. Сун. Словесная представимость триангуляций цилиндрических графов с сеткой, Дискр. Appl. Математика. 213 (2016), 60-70.
  9. Г.-С. Чеон, Дж. Ким, М. Ким, С. Китаев. Словесная представимость графов Теплица, Discr. Appl. Math., Чтобы появиться.
  10. Г.-С. Чеон, Дж. Ким, М. Ким, А. Пяткин. На k-11-представимые графы. J. Combin. 10 (2019) 3, 491-513.
  11. И. Чой, Дж. Ким и М. Ким. Об операциях, сохраняющих полупереходную ориентируемость графов, Журнал комбинаторной оптимизации 37 (2019) 4, 1351−1366.
  12. А. Коллинз, С. Китаев, В. Лозин. Новые результаты о графах, представимых в виде слов, Discr. Appl. Математика. 216 (2017), 136–141.
  13. А. Дайгаване, М. Сингх, Б.К. Джордж. 2-единообразные слова: циклические графы и алгоритм проверки конкретных словесных представлений графов. arXiv: 1806.04673 (2018).
  14. М. Гаец и К. Джи. Перечисление и расширения графов, представимых в виде слов. Конспект лекций по информатике 11682 (2019) 180−192. В R. Mercas, D. Reidenbach (Eds) Combinatorics on Words. СЛОВА 2019.
  15. М. Гаец и К. Джи. Перечень и расширения словесных представителей, arXiv: 1909.00019.
  16. М. Гаец и К. Джи. Перечисление и расширения словесных представителей, Комбинаторика слов, 180–192, Конспекты лекций по вычисл. Sci., 11682, Springer, Cham, 2019.
  17. А. Гао, С. Китаев, П. Чжан. О 132-представимых графах. Австралазийский J. Combin. 69 (2017), 105-118.
  18. М. Глен. Раскрашиваемость и словесная представимость почти триангуляций, чистой и прикладной математики, должны появиться в 2019 году.
  19. М. Глен. О представимости полимино триангуляций и графов в виде слов, 2019. Кандидатская диссертация, Университет Стратклайда.
  20. М. Глен и С. Китаев. Представимость в виде слов триангуляций прямоугольного полимино с одной плиткой домино, Журн. Комб. Мат. Комбинировать. Comput. 100, 131–144, 2017.
  21. М. Глен, С. Китаев, А. Пяткин. О представительном числе графа короны Discr. Appl. Математика. 244, 2018, 89-93.
  22. М.М. Халлдорссон, С. Китаев, А. Пяткин О представимых графах, полупереходных ориентациях и числах представления, arXiv: 0810.0310 (2008).
  23. М.М. Халлдорссон, С. Китаев, А. Пяткин (2010) Графы, фиксирующие чередования слов. В: Ю. Гао, Х. Лу, С. Секи, С. Ю (ред.), Развитие теории языка. DLT 2010. Конспект лекций. Sci. 6224, Спрингер, 436−437.
  24. М.М. Халлдорссон, С. Китаев, А. Пяткин (2011) Графы чередования. В: П. Колман, Дж. Кратохвил (ред.), Теоретико-графические концепции в компьютерных науках. WG 2011. Lecture Notes Comp. Sci. 6986, Спрингер, 191–202.
  25. М. Халлдорссон, С. Китаев, А. Пяткин. Полутранзитивные ориентации и графы, представимые в виде слов, Discr. Appl. Математика. 201 (2016), 164−171.
  26. М. Джонс, С. Китаев, А. Пяткин, Дж. Реммель. Представление графиков с помощью шаблонов без слов, Электрон. J. Combin. 22 (2), Рез. Пап. P2.53, 1-20 (2015).
  27. С. Китаев. О графах с числом представления 3, J. Autom., Lang. и Комбинировать. 18 (2013), 97−112.
  28. С. Китаев. Исчерпывающее введение в теорию графов, представимых в виде слов. В: Э. Шарлье, Дж. Лерой, М. Риго (ред.), Развитие теории языка. DLT 2017. Конспект лекций. Sci. 10396, Springer, 36–67.
  29. С. Китаев. Существование u-представления графов, Journal of Graph Theory 85 (2017) 3, 661-668.
  30. С. Китаев, Ю. Лонг, Дж. Ма, Х. Ву. Представимость разбитых графов в виде слов, arXiv: 1709.09725 (2017).
  31. С. Китаев, В. Лозин. Слова и графики, Springer, 2015. ISBN  978-3-319-25859-1.
  32. С. Китаев, А. Пяткин. О представимых графах, J. Autom., Lang. и Комбинировать. 13 (2008), 45−54.
  33. С. Китаев, А. Пяткин. Графы, представленные в виде слов: Обзор, Журнал прикладной и промышленной математики 12 (2) (2018) 278-296.
  34. С. Китаев, А. Пяткин. О полупереходной ориентируемости графов без треугольников, arXiv: 2003.06204v1.
  35. С. Китаев, А. Сайто. О полупереходной ориентируемости графов Кнезера и их дополнений, Discrete Math., Чтобы появиться.
  36. С. Китаев, П. Салимов, К. Северс, Х. Эльфарссон (2011) О представимости линейных графов. В: Г. Маури, А. Лепорати (ред.), Развитие теории языка. DLT 2011. Конспект лекций Comp. Sci. 6795, Спрингер, 478−479.
  37. С. Китаев, С. Сеиф. Словесная проблема полугруппы Перкинса через ориентированные ациклические графы, Заказ 25 (2008), 177-194.
  38. Э. Лелуп. Графики представляют собой однозначно. Магистерская работа, Льежский университет, 2019 г.
  39. Мандельштам. О графах, представленных словами, избегающими шаблонов, Discussiones Mathematicae Graph Theory 39 (2019) 375-389.
  40. С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25, номер 2, 19−53.

Программного обеспечения

Программное обеспечение для изучения графов, представленных в виде слов, можно найти здесь:

  1. М. Глен. Программное обеспечение для работы со словесными графами, 2017. Доступно по адресу https://personal.cis.strath.ac.uk/sergey.kitaev/word-presentable-graphs.html.
  2. H. Zantema. Программное обеспечение REPRNR для вычисления числа представления графа, 2018 г. Доступно по адресу https://www.win.tue.nl/~hzantema/reprnr.html.

использованная литература

  1. ^ а б c С. Китаев, С. Сеиф. Словесная проблема полугруппы Перкинса через ориентированные ациклические графы, Заказ 25 (2008), 177-194.
  2. ^ а б c d е ж г час я j С. Китаев, В. Лозин. Слова и графики, Springer, 2015. ISBN  978-3-319-25859-1
  3. ^ а б c С. Китаев, А. Пяткин. О представимых графах, J. Autom., Lang. и Комбинировать. 13 (2008), 45−54.
  4. ^ а б М.М. Халлдорссон, С. Китаев, А. Пяткин (2010) Графы, фиксирующие чередования слов. В: Ю. Гао, Х. Лу, С. Секи, С. Ю (ред.), Развитие теории языка. DLT 2010. Конспект лекций. Sci. 6224, Спрингер, 436−437.
  5. ^ а б c М.М. Халлдорссон, С. Китаев, А. Пяткин (2011) Графы чередования. В: П. Колман, Дж. Кратохвил (ред.), Теоретико-графические концепции в компьютерных науках. WG 2011. Lecture Notes Comp. Sci. 6986, Спрингер, 191–202.
  6. ^ а б c d е ж г М. Халлдорссон, С. Китаев, А. Пяткин. Полутранзитивные ориентации и графы, представимые в виде слов, Discr. Appl. Математика. 201 (2016), 164−171.
  7. ^ а б c d С. Китаев. Подробное введение в теорию графов, представимых в виде слов. В: Э. Шарлье, Дж. Лерой, М. Риго (ред.), Развитие теории языка. DLT 2017. Конспект лекций. Sci. 10396, Springer, 36–67.
  8. ^ а б С. Китаев, А. Пяткин. Графы, представленные в виде слов: Обзор, Журнал прикладной и промышленной математики 12 (2) (2018) 278-296.
  9. ^ а б С. В. Китаев, А. В. Пяткин. Графы, представимые в виде слов. Обзор результатов, Дискретн. анализ и исслед. опер., 2018, том 25, номер 2, 19−53
  10. ^ А. Коллинз, С. Китаев, В. Лозин. Новые результаты о графах, представимых в виде слов, Discr. Appl. Математика. 216 (2017), 136–141.
  11. ^ Ö. Акгюн, И. Гент, С. Китаев, Х. Зантема. Решение вычислительных задач теории графов, представимых в виде слов. Журнал целочисленных последовательностей 22 (2019), статья 19.2.5.
  12. ^ а б c d Т. З. К. Чен, С. Китаев, А. Сайто. Представление разбитых графов словами, arXiv: 1909.09471
  13. ^ а б И. Чой, Дж. Ким и М. Ким. Об операциях, сохраняющих полупереходную ориентируемость графов, Журнал комбинаторной оптимизации 37 (2019) 4, 1351−1366.
  14. ^ а б Ö. Акгюн, И. Гент, С. Китаев, Х. Зантема. Решение вычислительных задач теории графов, представимых в виде слов. Журнал целочисленных последовательностей 22 (2019), статья 19.2.5.
  15. ^ а б М. Глен, С. Китаев, А. Пяткин. О представительном числе графа короны Discr. Appl. Математика. 244, 2018, 89–93.
  16. ^ а б М. Глен. Раскрашиваемость и словесная представимость почти триангуляций, чистой и прикладной математики, должны появиться в 2019 году.
  17. ^ П. Акроботу, С. Китаев, З. Масарова. О представимости полимино триангуляций в виде слов. Сибирский Adv. Математика. 25 (2015), 1-10.
  18. ^ М. Глен и С. Китаев. Представимость в виде слов триангуляций прямоугольного полиамино с одной плиткой домино, Журн. Комб. Мат. Комбинировать. Comput. 100, 131–144, 2017.
  19. ^ Т. З. К. Чен, С. Китаев, Б. Ю. Сун. Словесная представимость подразделов граней треугольных сеточных графов, Graphs и Combin. 32 (5) (2016), 1749−1761.
  20. ^ Т. З. К. Чен, С. Китаев, Б. Ю. Сун. Словесная представимость триангуляций цилиндрических графов с сеткой, Дискр. Appl. Математика. 213 (2016), 60-70.
  21. ^ а б c С. Китаев, Ю. Лонг, Дж. Ма, Х. Ву. Представимость разбитых графов в виде слов, arXiv: 1709.09725 (2017).
  22. ^ А. Гао, С. Китаев, П. Чжан. О 132-представимых графах. Австралазийский J. Combin. 69 (2017), 105-118.
  23. ^ Мандельштам. О графах, представленных словами, избегающими шаблонов, Discussiones Mathematicae Graph Theory 39 (2019) 375-389.
  24. ^ М. Джонс, С. Китаев, А. Пяткин, Дж. Реммель. Представление графиков с помощью шаблонов без слов, Электрон. J. Combin. 22 (2), Рез. Пап. P2.53, 1-20 (2015).
  25. ^ М. Гаец и К. Джи. Перечисление и расширения графов, представимых в виде слов. Конспект лекций по информатике 11682 (2019) 180−192. В R. Mercas, D. Reidenbach (Eds) Combinatorics on Words. СЛОВА 2019.
  26. ^ М. Гаец и К. Джи. Перечень и расширения словесных представителей, arXiv: 1909.00019.
  27. ^ С. Китаев. Существование u-представления графов, Journal of Graph Theory 85 (2017) 3, 661-668.
  28. ^ а б Г.-С. Чеон, Дж. Ким, М. Ким, А. Пяткин. На k-11-представимые графы. J. Combin. 10 (2019) 3, 491-513.
  29. ^ С. Китаев. О графах с числом представления 3, J. Autom., Lang. и Комбинировать. 18 (2013), 97−112.