Гомоморфизм графов

Сохраняющее структуру соответствие между графами узлов и связей.

Гомоморфизм цветочного снарка J ₅ в граф циклов C ₅ .
Это также ретракция на подграф по пяти центральным вершинам. Таким образом, J ₅ фактически гомоморфно эквивалентен с- ядру C ₅ .

В математической области теории графов гомоморфизм графов — это отображение между двумя графами , которое учитывает их структуру. Более конкретно, это функция между множествами вершин двух графов, которая отображает соседние вершины в соседние вершины.

Гомоморфизмы обобщают различные понятия раскраски графов и позволяют выражать важный класс проблем удовлетворения ограничений , таких как определенные проблемы планирования или назначения частот . ^[1] Тот факт, что гомоморфизмы могут быть составлены, приводит к богатым алгебраическим структурам: предпорядку на графах, дистрибутивной решетке и категории (одна для неориентированных графов и одна для ориентированных графов). ^[2] Вычислительная сложность поиска гомоморфизма между заданными графами в целом непомерно высока, но известно много о частных случаях, разрешимых за полиномиальное время . Границы между поддающимися и трудноразрешимыми случаями были активной областью исследований. ^[3]

Определения

В этой статье, если не указано иное, графы являются конечными, неориентированными графами с петлями разрешены, но кратные ребра (параллельные ребра) запрещены. Гомоморфизм графа [ ^4] f   из графа в граф , записанный ${\displaystyle G=(V(G),E(G))}$ ${\displaystyle H=(V(H),E(H))}$

ж  : Г → Ч

— функция от до , сохраняющая ребра. Формально подразумевает , для всех пар вершин в . Если существует какой-либо гомоморфизм из G в H , то G называется гомоморфной H или H -раскрашиваемой . Это часто обозначается как просто ${\displaystyle V(G)}$ ${\displaystyle V(H)}$ ${\displaystyle (u,v)\in E(G)}$ ${\displaystyle (f(u),f(v))\in E(H)}$ ${\displaystyle u,v}$ ${\displaystyle V(G)}$

Г → Ч .

Приведенное выше определение распространяется на ориентированные графы. Тогда для гомоморфизма f  : G → H , ( f ( u ), f ( v )) является дугой (направленным ребром) H , если ( u , v ) является дугой G .

Существует инъективный гомоморфизм из G в H (т . е. тот , который отображает различные вершины в G в различные вершины в H ) тогда и только тогда, когда G изоморфен подграфу H . Если гомоморфизм f  : G → H является биекцией и его обратная функция f ⁻¹ также является гомоморфизмом графа, то f является изоморфизмом графа. ^[5]

Накрывающие карты представляют собой особый вид гомоморфизмов, которые отражают определение и многие свойства накрывающих карт в топологии . ^[6] Они определяются как сюръективные гомоморфизмы (т.е. что-то отображается в каждую вершину), которые также являются локально биективными, то есть биекциями в окрестности каждой вершины. Примером может служить двудольное двойное покрытие , _{сформированное} из графа путем разделения каждой вершины v на v0 и v1 _и замены _{каждого ребра} u , v ребрами u0 , v1 и _{v0 ,} u1 . Функция, отображающая v ₀ и v ₁ в накрытии в v в исходном графе, является гомоморфизмом и накрывающим отображением.

Гомеоморфизм графов — это другое понятие, не связанное напрямую с гомоморфизмами. Грубо говоря, он требует инъективности, но позволяет отображать ребра в пути (а не только в ребра). Миноры графов — еще более расслабленное понятие.

Ядра и ретракты

K ₇ , полный граф с 7 вершинами, является ядром.

Два графа G и H гомоморфно эквивалентны , если G → H и H → G . ^[4] Отображения не обязательно являются сюръективными или инъективными. Например, полные двудольные графы K _2,2 и K _3,3 гомоморфно эквивалентны: каждое отображение можно определить как взятие левой (соответственно правой) половины графа области и отображение только одной вершины в левой (соответственно . справа) половина графика изображения.

Ретракция — это гомоморфизм r графа G в подграф H графа G такой, что r ( v ) = v для каждой вершины v графа H. В этом случае подграф H называется ретрактом G . ^[7]

Ядро — это граф, не имеющий гомоморфизма ни одному собственному подграфу . Эквивалентно, ядро ​​можно определить как граф, который не сводится ни к одному подграфу. ^[8] Каждый граф G гомоморфно эквивалентен единственному ядру (с точностью до изоморфизма), называемому ядром G . ^[9] Примечательно, что это в целом неверно для бесконечных графов. ^[10] Однако те же определения применимы и к ориентированным графам, и ориентированный граф также эквивалентен уникальному ядру. Каждый граф и каждый ориентированный граф содержит свое ядро ​​в виде ретракта и индуцированного подграфа . ^[7]

Например, все полные графы K _n и все нечетные циклы ( графы циклов нечетной длины) являются ядрами. Любой 3-раскрашиваемый граф G , содержащий треугольник (т. е. имеющий полный граф K ₃ в качестве подграфа), гомоморфно эквивалентен K ₃ . Это связано с тем, что, с одной стороны, 3-раскраска G — это то же самое, что гомоморфизм G → K ₃ , как объяснено ниже. С другой стороны, каждый подграф G тривиально допускает гомоморфизм в G , _откуда следует K3 → G. Это также означает, что K ₃ является ядром любого такого графа G . Аналогично, каждый двудольный граф , имеющий хотя бы одно ребро, эквивалентен K ₂ . ^[11]

Подключение к раскраскам

k -раскраска для некоторого целого числа k — это назначение одного из k цветов каждой вершине графа G так , что концы каждого ребра приобретают разные цвета. k -раскраски G в _{точности} соответствуют гомоморфизмам G в полный граф Kk . ^[12] Действительно, вершины K _k соответствуют k цветам, и два цвета смежны как вершины K _k тогда и только тогда, когда они различны. Следовательно, функция определяет гомоморфизм K _k тогда и только тогда, когда она отображает смежные вершины G в разные цвета (т. е. является k -раскраской). В частности, G является k -раскрашиваемой тогда и только тогда, когда она K _k -раскрашиваема. ^[12]

Если существуют два гомоморфизма G → H и H → Kk _, то их композиция G → Kk также _{является} гомоморфизмом. ^[13] Другими словами, если граф H можно раскрасить в k цветов и существует гомоморфизм из G в H , то G также может быть k -цветом. Следовательно, из G → H следует χ( G ) ⩽ χ( H ), где χ обозначает хроматическое число графа (наименьшее k , для которого он k -раскрашиваем). ^[14]

Варианты

Общие гомоморфизмы также можно рассматривать как своего рода раскраску: если вершины фиксированного графа H являются доступными цветами , а ребра H описывают, какие цвета совместимы , то H -раскраска графа G — это присвоение цветов вершинам графа H. G так, чтобы соседние вершины имели совместимые цвета. Многие понятия раскраски графов вписываются в этот шаблон и могут быть выражены как гомоморфизмы графов в различные семейства графов. Круговые раскраски можно определить с помощью гомоморфизмов в круговые полные графы , уточняя обычное понятие раскрасок. ^[15] Дробная и b -кратная раскраска может быть определена с помощью гомоморфизмов в графы Кнезера . ^[16] T-раскраски соответствуют гомоморфизмам в некоторые бесконечные графы. ^[17] Ориентированная раскраска ориентированного графа является гомоморфизмом любого ориентированного графа . ^[18] L (2,1)-раскраска — это гомоморфизм в дополнение к графу путей , который является локально инъективным, то есть он должен быть инъективным в окрестности каждой вершины. ^[19]

Ориентации без длинных путей

Другая интересная связь касается ориентации графов. Ориентацией неориентированного графа G называется любой ориентированный граф, полученный выбором одной из двух возможных ориентаций для каждого ребра. Примером ориентации полного графа K _k является транзитивный турнир T → _k с вершинами 1, 2,…, k и дугами от i до j всякий раз, когда i < j . Гомоморфизм между ориентациями графов G и H дает гомоморфизм между неориентированными графами G и H просто за счет игнорирования ориентаций. С другой стороны, при наличии гомоморфизма G → H между неориентированными графами любую ориентацию H → графа H можно вернуть обратно к ориентации G → графа G, так что G → имеет гомоморфизм к H → . Следовательно, граф G является k -раскрашиваемым (имеет гомоморфизм в K _k ) тогда и только тогда, когда некоторая ориентация G имеет гомоморфизм в T → _k . ^[20]

Фольклорная теорема утверждает, что для всех k ориентированный граф G имеет гомоморфизм T → _k тогда и только тогда, когда он не допускает гомоморфизма направленного пути P → _{k +1} . ^[21] Здесь P → _n — ориентированный граф с вершинами 1, 2, …, n и ребрами от i до i + 1, для i = 1, 2, …, n − 1. Следовательно, граф k -раскрашиваем. тогда и только тогда, когда он имеет ориентацию, не допускающую гомоморфизма из P → _{k +1} . Это утверждение можно немного усилить, сказав, что граф является k -раскрашиваемым тогда и только тогда, когда некоторая ориентация не содержит направленного пути длины k (нет P → _{k +1} в качестве подграфа). Это теорема Галлаи–Хассе–Роя–Витавера .

Связь с проблемами удовлетворения ограничений

Примеры

Граф H непоследовательных дней недели, изоморфный графу дополнений C 7 _и круговой клике K _7/2

Некоторые проблемы планирования можно смоделировать как вопрос о поиске гомоморфизмов графов. ^{[22] [23]} Например, можно захотеть назначить курсы семинаров временным интервалам в календаре, чтобы два курса, посещаемые одним и тем же студентом, не были слишком близки друг к другу во времени. Курсы образуют граф G с ребром между любыми двумя курсами, которые посещает какой-то обычный студент. Временные интервалы образуют граф H с ребром между любыми двумя интервалами, достаточно удаленными во времени. Например, если кто-то хочет циклический еженедельный график, при котором каждый студент посещает курсы семинаров в непоследовательные дни, тогда H будет графом дополнения C ₇ . Гомоморфизм графа от G до H представляет собой расписание, распределяющее курсы по временным интервалам, как указано. ^[22] Чтобы добавить требование о том, что, например, ни у одного студента нет занятий одновременно в пятницу и понедельник, достаточно удалить соответствующее ребро из H .

Простую задачу распределения частот можно сформулировать следующим образом: несколько передатчиков в беспроводной сети должны выбрать частотный канал, по которому они будут передавать данные. Чтобы избежать помех , передатчики, находящиеся географически близко, должны использовать каналы с частотами, которые находятся далеко друг от друга. Если это условие аппроксимируется одним порогом для определения «географически близко» и «далеко друг от друга», то правильный выбор канала снова соответствует гомоморфизму графа. Он должен перейти от графа передатчиков G , с ребрами между парами, географически близкими, к графу каналов H , с ребрами между каналами, расположенными далеко друг от друга. Хотя эта модель довольно упрощена, она допускает некоторую гибкость: пары передатчиков, которые не расположены близко, но могут создавать помехи из-за географических особенностей , могут быть добавлены к краям G. Тех, кто при этом не общается, можно из него удалить. Аналогично, пары каналов, которые находятся далеко друг от друга, но имеют гармонические помехи, могут быть удалены из набора ребер H . ^[24]

В каждом случае эти упрощенные модели отражают множество проблем, которые приходится решать на практике. ^[25] Проблемы удовлетворения ограничений , которые обобщают проблемы гомоморфизма графов, могут выражать различные дополнительные типы условий (такие как индивидуальные предпочтения или границы числа совпадающих назначений). Это позволяет сделать модели более реалистичными и практичными.

Формальный вид

Графы и ориентированные графы можно рассматривать как частный случай гораздо более общего понятия, называемого реляционными структурами (определяемыми как набор с кортежем отношений на нем). Ориентированные графы — это структуры с одним бинарным отношением (смежностью) в области (множестве вершин). ^{[26] [3]} Согласно этой точке зрения, гомоморфизмы таких структур являются в точности гомоморфизмами графов. В общем, вопрос нахождения гомоморфизма одной реляционной структуры в другую представляет собой проблему удовлетворения ограничений (CSP). Случай с графами дает конкретный первый шаг, который помогает понять более сложные CSP. Многие алгоритмические методы поиска гомоморфизмов графов, такие как возврат с возвратом , распространение ограничений и локальный поиск , применимы ко всем CSP. ^[3]

Для графов G и H вопрос о том, имеет ли G гомоморфизм к H , соответствует экземпляру CSP только с одним видом ограничений, ^[3] следующим образом. Переменные являются вершинами G , а областью определения каждой переменной является множество вершин H . Оценка — это функция, которая присваивает каждой переменной элемент области определения, то есть функция f от V ( G ) до V ( H ). Каждое ребро или дуга ( u , v ) G тогда соответствует ограничению (( u , v ), E( H )). Это ограничение, выражающее, что вычисление должно отображать дугу ( u , v ) в пару ( f ( u ), f ( v ) ), которая находится в отношении E ( H ), то есть в дугу H . Решением CSP является оценка, которая учитывает все ограничения, поэтому это в точности гомоморфизм из G в H .

Структура гомоморфизмов

Композиции гомоморфизмов являются гомоморфизмами. ^[13] В частности, отношение → на графах транзитивно (и рефлексивно, тривиально), поэтому оно является предпорядком на графах. ^[27] Пусть класс эквивалентности графа G при гомоморфной эквивалентности равен [ G ]. Класс эквивалентности также может быть представлен уникальным ядром в [ G ]. Отношение → является частичным порядком в этих классах эквивалентности; он определяет частично упорядоченный набор . ^[28]

Пусть G < H означает , что существует гомоморфизм из G в H , но нет гомоморфизма из H в G. Отношение → является плотным порядком , что означает, что для всех (неориентированных) графов G , H таких, что G < H , существует граф K такой, что G < K < H (это справедливо, за исключением тривиальных случаев G = K ₀ или К ₁ ). ^{[29] [30]} Например, между любыми двумя полными графами (кроме K ₀ , K ₁ , K ₂ ) существует бесконечно много круговых полных графов , соответствующих рациональным числам между натуральными числами. ^[31]

Частное множество классов эквивалентности графов при гомоморфизмах представляет собой дистрибутивную решетку с соединением [ G ] и [ H ], определяемым как (класс эквивалентности) непересекающегося объединения [ G ∪ H ] и пересечения [ G ] и [ H ] определяется как тензорное произведение [ G × H ] (выбор графов G и H , представляющих классы эквивалентности [ G ] и [ H ] не имеет значения). ^[32] Неприводимые к объединению элементы этой решетки представляют собой точно связные графы. Это можно показать, используя тот факт, что гомоморфизм отображает связный граф в один связный компонент целевого графа. ^{[33] [34]} Неприводимые элементы этой решетки — это в точности мультипликативные графы . Это графы K такие, что произведение G × H имеет гомоморфизм к K только тогда, когда один из G или H также гомоморфен. Идентификация мультипликативных графов лежит в основе гипотезы Хедетниеми . ^{[35] [36]}

Гомоморфизмы графов также образуют категорию , в которой графы являются объектами, а гомоморфизмы — стрелками. ^[37] Начальным объектом является пустой граф, а конечным объектом является граф с одной вершиной и одним циклом в этой вершине. Тензорное произведение графов — это теоретико-категорное произведение , а экспоненциальный граф — это экспоненциальный объект для этой категории. ^{[36] [38]} Поскольку эти две операции всегда определены, категория графов является декартовой замкнутой категорией . По той же причине решетка классов эквивалентности графов относительно гомоморфизмов фактически является алгеброй Гейтинга . ^{[36] [38]}

Для ориентированных графов применяются те же определения. В частности, → является частичным порядком на классах эквивалентности ориентированных графов. Он отличается от порядка → на классах эквивалентности неориентированных графов, но содержит его как подпорядок. Это связано с тем, что каждый неориентированный граф можно рассматривать как ориентированный граф, где каждая дуга ( u , v ) появляется вместе со своей обратной дугой ( v , u ), и это не меняет определения гомоморфизма. Порядок → для ориентированных графов снова представляет собой дистрибутивную решетку и алгебру Гейтинга с операциями соединения и встречи, определенными, как и раньше. Однако он не плотный. Существует также категория с ориентированными графами в качестве объектов и гомоморфизмами в виде стрелок, которая снова является декартовой замкнутой категорией . ^{[39] [38]}

Несравненные графики

Граф Грётча, несравнимый с K ₃

Существует множество несравнимых графов относительно предпорядка гомоморфизма, то есть пар графов, ни один из которых не допускает гомоморфизма в другой. ^[40] Один из способов их построения — рассмотреть нечетный обхват графа G , длину его кратчайшего цикла нечетной длины. Нечетный обхват, эквивалентно, представляет собой наименьшее нечетное число g , для которого существует гомоморфизм графа цикла на g вершинах в G . По этой причине, если G → H , то нечетный обхват G больше или равен нечетному обхвату H. ^[41]

С другой стороны, если G → H , то хроматическое число G меньше или равно хроматическому числу H. Следовательно, если G имеет строго больший нечетный обхват, чем H, и строго большее хроматическое число, чем H , то G и H несравнимы. ^[40] Например, граф Греча 4-хроматичен и не содержит треугольников (он имеет обхват 4 и нечетный обхват 5), ^[42] поэтому он несравним с треугольным графом K ₃ .

Примерами графов со сколь угодно большими значениями нечетного обхвата и хроматического числа являются графы Кнезера ^[43] и обобщенные мицельскианы . ^[44] Последовательность таких графов при одновременно возрастающих значениях обоих параметров дает бесконечное число несравнимых графов ( антицепь в предпорядке гомоморфизма). ^[45] Другие свойства, такие как плотность предпорядка гомоморфизма, могут быть доказаны с использованием таких семейств. ^[46] Возможны также конструкции графов с большими значениями хроматического числа и обхвата, а не только нечетного обхвата, но более сложные (см. Обхват и раскраска графа ).

Среди ориентированных графов гораздо легче найти несравнимые пары. Например, рассмотрим ориентированные графы циклов C → _n с вершинами 1, 2, …, n и ребрами от i до i + 1 (для i = 1, 2, …, n − 1) и от n до 1. Там является гомоморфизмом из C → _n в C → _k ( n , k ≥ 3) тогда и только тогда, когда n кратно k . В частности, все графы ориентированных циклов C → _n с n простыми числами несравнимы. ^[47]

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

В проблеме гомоморфизма графов экземпляром является пара графов ( G , H ) , а решением является гомоморфизм из G в H. Общая задача решения , в которой спрашивается, существует ли какое-либо решение, является NP-полной . ^[48] ​​Однако ограничение разрешенных случаев порождает множество различных проблем, некоторые из которых гораздо проще решить. Методы, применяемые при ограничении левой стороны G, сильно отличаются от методов для правой стороны H , но в каждом случае известна или предполагается дихотомия (резкая граница между легкими и трудными случаями).

Гомоморфизмы фиксированного графа

Проблема гомоморфизма с фиксированным графом H в правой части каждого экземпляра также называется проблемой H -раскраски. Когда H — полный граф K _k , это проблема k -раскраски графа , которая разрешима за полиномиальное время для k = 0, 1, 2 и NP-полна в противном случае. ^[49] В частности, K ₂ -раскрашиваемость графа G эквивалентна тому, что G является двудольным , что можно проверить за линейное время. В более общем смысле, когда H является двудольным графом, H -раскраска эквивалентна K ₂ -раскраске (или K ₀ / K ₁ -раскраске, когда H пуст/без ребер), поэтому решение одинаково легко принять. ^[50] Павол Хелл и Ярослав Нешетржил доказали, что для неориентированных графов ни один другой случай неразрешим:

Теорема Хелла – Нешетрила (1990): проблема H -раскраски возникает в P, когда H двудольна, и NP-полна в противном случае. ^{[51] [52]}

Это также известно как теорема дихотомии для (неориентированных) гомоморфизмов графов, поскольку она делит задачи H -раскраски на NP-полные или P-задачи без промежуточных случаев. Для ориентированных графов ситуация более сложная и фактически эквивалентна гораздо более общему вопросу характеристики сложности задач удовлетворения ограничений . ^[53] Оказывается, что задачи H -раскраски ориентированных графов столь же общие и разнообразные, как и задачи CSP с любыми другими видами ограничений. ^{[54] [55]} Формально (конечный) язык ограничений (или шаблон ) Γ представляет собой конечную область и конечное множество отношений над этой областью. CSP( Γ ) — это проблема удовлетворения ограничений, где экземплярам разрешено использовать только ограничения в Γ .

Теорема (Федер, Варди , 1998): Для каждого языка ограничений Γ проблема CSP( Γ ) эквивалентна при полиномиальном сокращении времени некоторой задаче H -раскраски для некоторого ориентированного графа H . ^[55]

Интуитивно это означает, что любой алгоритмический метод или результат сложности, применимый к задачам H -раскраски для ориентированных графов H, также применим и к общим CSP. В частности, можно задаться вопросом, можно ли распространить теорему Хелла–Нешетрила на ориентированные графы. Согласно приведенной выше теореме, это эквивалентно гипотезе Федера-Варди (также известной как гипотеза CSP, гипотеза дихотомии) о дихотомии CSP, которая утверждает, что для каждого языка ограничений Γ CSP( Γ ) является NP-полным или в P. ^[48] Эта гипотеза была доказана в 2017 году независимо Дмитрием Жуком и Андреем Булатовым, что привело к следующему следствию:

Следствие (Булатов 2017; Жук 2017): Задача H -раскраски ориентированных графов при фиксированном H является либо P-, либо NP-полной.

Гомоморфизмы фиксированного семейства графов

Проблема гомоморфизма с единственным фиксированным графом G в левой части входных экземпляров может быть решена методом перебора за время | В ( Ч ) | ^{O(| V ( G )|)} , поэтому полиномиален по размеру входного графа H . ^[56] Другими словами, проблема тривиально решается в P для графов G ограниченного размера. Тогда возникает интересный вопрос: какие еще свойства G , помимо размера, делают возможными полиномиальные алгоритмы?

Важнейшим свойством оказывается ширина дерева , мера того, насколько древовидным является граф. Для графа G древовидной ширины не более k и графа H проблема гомоморфизма может быть решена за время | В ( Ч ) | ^{O( k )} со стандартным подходом динамического программирования . На самом деле достаточно предположить, что ядро ​​группы G имеет ширину дерева не более k . Это справедливо, даже если ядро ​​неизвестно. ^{[57] [58]}

Показатель в | В ( Ч ) | Алгоритм с временем работы ^{O( k )} не может быть значительно уменьшен: ни один алгоритм со временем работы | В ( Ч ) | ^{o(tw( G ) /log tw( G ))} существует, предполагая гипотезу экспоненциального времени (ETH), даже если входные данные ограничены любым классом графов неограниченной ширины дерева. ^[59] ETH — это недоказанное предположение, похожее на P ≠ NP , но более сильное. При том же предположении практически не существует других свойств, которые можно было бы использовать для получения алгоритмов с полиномиальным временем. Это формализуется следующим образом:

Теорема ( Гроэ ): Для вычислимого класса графов проблема гомоморфизма для экземпляров с находится в P тогда и только тогда, когда графы в имеют ядра ограниченной ширины дерева (при условии ETH). ^[58] ${\displaystyle {\mathcal {G}}}$ ${\displaystyle (G,H)}$ ${\displaystyle G\in {\mathcal {G}}}$ ${\displaystyle {\mathcal {G}}}$

Можно задаться вопросом , разрешима ли проблема хотя бы за время, сколь угодно сильно зависящее от G , но с фиксированной полиномиальной зависимостью от размера H. Ответ снова будет положительным, если мы ограничим G классом графов с ядрами ограниченной ширины дерева, и отрицательным для любого другого класса. ^[58] На языке параметризованной сложности это формально означает, что проблема гомоморфизма, параметризованная размером (количеством ребер) G , демонстрирует дихотомию. Он является управляемым с фиксированными параметрами, если графы в имеют ядра ограниченной ширины дерева, и W[1] -полны в противном случае. ${\displaystyle {\mathcal {G}}}$ ${\displaystyle {\mathcal {G}}}$

Те же утверждения в более общем плане справедливы и для задач удовлетворения ограничений (или, другими словами, для реляционных структур). Единственное необходимое предположение состоит в том, что ограничения могут включать только ограниченное число переменных (все отношения имеют некоторую ограниченную арность, 2 в случае графов). Соответствующим параметром тогда является ширина дерева основного графа ограничений . ^[59]

Смотрите также

• Глоссарий терминов теории графов
• Гомоморфизм для одного и того же понятия в разных алгебраических структурах.
• Переписывание графа
• Медианные графики , определяемые как ретракты гиперкубов.
• Гипотеза Сидоренко

Примечания

1. Ад и Нешетржил 2004, с. 27.
2. Ад и Нешетржил 2004, с. 109.
3. Hell & Nešetřil 2008.
4. Введение см. (в порядке увеличения длины): Cameron (2006); Хан и Тардиф (1997); Ад и Нешетржил (2004).
5. Хан и Тардиф 1997, Наблюдение 2.3.
6. Годсил и Ройл 2001, с. 115.
7. Hell & Nešetřil 2004, с. 19.
8. Ад и Нешетржил 2004, Предложение 1.31.
9. Кэмерон 2006, Предложение 2.3; Ад и Нешетржил 2004, следствие 1.32.
10. Ад и Нешетржил 2004, с. 34.
11. Кэмерон 2006, с. 4, предложение 2.5.
12. Кэмерон 2006, с. 1; Ад и Нешетржил 2004, Предложение 1.7.
13. Hell & Nešetřil 2004, §1.7.
14. Ад и Нешетржил 2004, Следствие 1.8.
15. Ад и Нешетржил 2004, §6.1; Хан и Тардиф 1997, §4.4.
16. Ад и Нешетржил 2004, §6.2; Хан и Тардиф 1997, §4.5.
17. Ад и Нешетржил 2004, §6.3.
18. Ад и Нешетржил 2004, §6.4.
19. Фиала, Дж.; Кратохвил, Дж. (2002), «Частичные покрытия графов», Discountes Mathematicae Graph Theory , 22 (1): 89–99, doi : 10.7151/dmgt.1159, S2CID  17507393
20. Ад и Нешетржил 2004, стр. 13–14.
21. Ад и Нешетржил 2004, Предложение 1.20.
22. Кэмерон 2006, с. 1.
23. Ад и Нешетржил 2004, §1.8.
24. Ад и Нешетржил 2004, стр. 30–31.
25. Ад и Нешетржил 2004, стр. 31–32.
26. Ад и Нешетржил 2004, с. 28, обратите внимание, что реляционные структуры там называются реляционными системами .
27. Ад и Нешетржил 2004, §3.1.
28. Ад и Нешетржил 2004, Теорема 3.1.
29. Ад и Нешетржил 2004, Теорема 3.30; Хан и Тардиф 1997, Теорема 2.33.
30. Вельцль, Э. (1982), «Цветовые семейства плотны», Theoretical Computer Science , 17 : 29–41, doi : 10.1016/0304-3975(82)90129-3
31. Ад и Нешетржил 2004, с. 192; Хан и Тардиф 1997, с. 127.
32. Hell & Nešetřil 2004, Предложение 3.2, дистрибутивность указана в Предложении 2.4; Хан и Тардиф 1997, Теорема 2.37.
33. Квуида, Леонард; Лехтонен, Эркко (2011), «О порядке гомоморфизма помеченных ЧУМ», Order , 28 (2): 251–265, arXiv : 0911.0200 , doi : 10.1007/s11083-010-9169-x, S2CID  14920600
34. Грей 2014, Лемма 3.7.
35. Тардиф, К. (2008), «Гипотеза Хедетниеми, 40 лет спустя» (PDF) , Заметки по теории графов в Нью-Йорке , 54 : 46–57, MR  2445666.
36. Дуайт, Д.; Зауэр, Н. (1996), «Решетки, возникающие при категориальных исследованиях гипотезы Хедетниеми», Discrete Mathematics , 152 (1–3): 125–139, doi : 10.1016/0012-365X(94)00298-W
37. Ад и Нешетржил 2004, с. 125.
38. Грей 2014.
39. Браун и др. 2008.
40. Hell & Nešetřil 2004, с. 7.
41. Хан и Тардиф 1997, Наблюдение 2.6.
42. Вайсштейн, Эрик В. , «График Грётча», MathWorld
43. Хан и Тардиф 1997, Предложение 3.14.
44. Дьярфас, А.; Дженсен, Т.; Штибиц, М. (2004), «О графах со строго независимыми цветовыми классами», Журнал теории графов , 46 (1): 1–14, doi : 10.1002/jgt.10165, S2CID  17859655
45. Ад и Нешетржил 2004, Предложение 3.4.
46. Ад и Нешетржил 2004, с. 96.
47. Ад и Нешетржил 2004, с. 35.
48. Бодирский 2007, §1.3.
49. Ад и Нешетржил 2004, §5.1.
50. Ад и Нешетржил 2004, Предложение 5.1.
51. Ад и Нешетржил 2004, §5.2.
52. Черт, Павол ; Нешетржил, Ярослав (1990), «О сложности H-раскраски», Журнал комбинаторной теории , серия B, 48 (1): 92–110, doi : 10.1016/0095-8956(90)90132-J
53. Ад и Нешетржил 2004, §5.3.
54. Ад и Нешетржил 2004, Теорема 5.14.
55. Федер, Томас; Варди, Моше Ю. (1998), «Вычислительная структура монотонного монадического SNP и удовлетворение ограничений: исследование с помощью журнала данных и теории групп», SIAM Journal on Computing , 28 (1): 57–104, doi : 10.1137/S0097539794266766
56. Сиган, Марек; Фомин Федор Владимирович ; Головнев Александр; Куликов, Александр С.; Михайлин Иван; Пачоцкий, Якуб; Сокала, Аркадиуш (2016), «Точные границы гомоморфизма графов и изоморфизма подграфов», Краутгеймер, Роберт (редактор), Труды двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2016, Арлингтон, Вирджиния, США , 10–12 января 2016 г. , Общество промышленной и прикладной математики , стр. 1643–1649, arXiv : 1507.03738 , doi : 10.1137/1.9781611974331.ch112, ISBN 978-1-611974-33-1
57. Далмау, Виктор; Колайтис, Фокион Г.; Варди, Моше Ю. (2002), «Удовлетворение ограничений, ограниченная ширина дерева и логика с конечной переменной», в Ван Хентенрик, Паскаль (ред.), Принципы и практика программирования с ограничениями - CP 2002, 8-я Международная конференция, CP 2002, Итака, Нью-Йорк, США, 9–13 сентября 2002 г., Труды , конспекты лекций по информатике, том. 2470, Springer, стр. 310–326, номер документа : 10.1007/3-540-46135-3_21.
58. Grohe, Мартин (2007), «Сложность проблем гомоморфизма и удовлетворения ограничений, взгляд с другой стороны», Journal of the ACM , 54 (1): 1–es, doi : 10.1145/1206035.1206036, S2CID  11797906
59. Маркс, Даниэль (2010), «Можете ли вы превзойти ширину дерева?», Теория вычислений , 6 : 85–112, doi : 10.4086/toc.2010.v006a005

Рекомендации

Общие книги и экспозиции

• Кэмерон, Питер (2006), Гомоморфизмы графов, Заметки группы по изучению комбинаторики (PDF)
• Черт, Павол ; Нешетржил, Ярослав (2004), Графы и гомоморфизмы, Оксфордская серия лекций по математике и ее приложениям, том. 28, Издательство Оксфордского университета, ISBN 0-19-852817-5
• Хан, Геня; Тардиф, Клод (1997), «Гомоморфизмы графов: структура и симметрия», Симметрия графов: алгебраические методы и приложения (PDF) , Springer, стр. 107–166, doi : 10.1007/978-94-015-8937-6_4
• Годсил, Крис ; Ройл, Гордон (2001), «6. Гомоморфизмы», Алгебраическая теория графов, Тексты для выпускников по математике, том. 207, Спрингер – Верлаг, Нью-Йорк, номер домена : 10.1007/978-1-4613-0163-9, ISBN. 978-1-4613-0163-9, S2CID  9661174
• Ловас, Ласло (2012). Большие сети и ограничения графов (PDF) . Провиденс, Род-Айленд: Американское математическое общество. ISBN 0-8218-9085-9.

В удовлетворении ограничений и универсальной алгебре

• Бодирский, Мануэль (2007), Гомоморфизмы графов и универсальная алгебра, конспекты курса (PDF)
• Черт, Павол ; Нешетржил, Ярослав (2008), «Раскраска, удовлетворение ограничений и сложность» (PDF) , Computer Science Review , 2 (3): 143–163, doi : 10.1016/j.cosrev.2008.10.003

В теории решеток и теории категорий

• Браун, Рональд; Моррис, Ифор; Шримптон, Джон; Уэнсли, Кристофер Д. (2008), «Графики морфизмов графов», Электронный журнал комбинаторики , 15 (1): A1, doi : 10.37236/919
• Грей, Чарльз Т. (2014), Решетка диграфа (PDF)( Стипендии AMSI на каникулы, исследовательский отчет студентов под руководством Брайана Дэйви и Джейн Питкетли, Университет Ла Троб ).