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

Гомоморфізм зі снарку «квітка» $J_{5}$ у цикл $C_{5}$. Це також ретракція в центральні п'ять вершин. Тоді $J_{5}$, фактично, гомоморфно еквівалентний ядру $C_{5}$.

Гомоморфізм графів — це відображення між двома графами, що не порушує структури. Конкретніше, це відображення між наборами вершин двох графів, яке відображає суміжні вершини в суміжні.

Гомоморфізми узагальнюють різні поняття розфарбовування графів і дозволяють формулювати важливі класи задач виконання обмежень, таких як деякі задачі складання розкладів або задачі розподілу радіочастот. Факт, що гомоморфізми можна використати послідовно, приводить до багатих алгебричних структур — передпорядку на графах, дистрибутивної ґратки і категорій (одна для неорієнтованих графів і одна для орієнтованих графів). Обчислювальна складність пошуку гомоморфізму між заданими графами в загальному випадку позамежна, але відомо багато окремих випадків, коли задача здійсненна за поліноміальний час. Межі між розв'язними і нездоланними випадками є галуззю активних досліджень.

Визначення

У цій статті, якщо не сказано інше, під графами розуміють скінченні неорієнтовані графи з дозволеними петлями, але кратні ребра (паралельні) не дозволені. Гомоморфізм $f$ з графу $G=(V(G),E(G))$ у граф $H=(V(H),E(H))$, що записується як

$f:G\to H$,

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

$G\to H$.

Визначення, наведене вище, поширюється на орієнтовані графи. Тоді для гомоморфізму $f:G\to H,(f(u),f(v))$ є дугою (орієнтованим ребром) графу $H$, коли $(u,v)$ є дугою графу $G$.

Існує ін'єктивний гомоморфізм з $G$ в $H$ (тобто відображення, яке ніколи не відображає різні вершини в одну) тоді і тільки тоді, коли $G$ є підграфом графу $H$. Якщо гомоморфізм $f:G\to H$ є бієкцією (відповідністю один-до-одного між вершинами графу $G$ і графу $H$) обернена функція якого є також гомоморфізмом графу, тоді $f$ є ізоморфізмом графів.

Накривні відображення є частим видом гомоморфізмів, який відбиває визначення і багато властивостей накриття в топології. Вони визначаються як сюр'єктивні гомоморфізми, які локально бієктивні, тобто є бієкція в околі кожної вершини. Прикладом є подвійне покриття двочастковим графом, утворене з графу розбиттям кожної вершини $v$ на $v_{0}$ і $v_{1}$ і заміною кожного ребра $u$, $v$ на два ребра $u_{0},v_{1}$ і $v_{0},u_{1}$. Функція, що відображає $v_{0}$ і $v_{1}$ у $v$ початкового графу, є гомоморфізмом і накривним відображенням.

Гомеоморфізм графу є окремим поняттям, не пов'язаним прямо з гомоморфізми. Грубо кажучи, він вимагає ін'єктивності, але дозволяє відображення ребер у шляхи (а не просто в ребра). Мінори графу залишаються слабшим поняттям.

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

$K_{7}$, повний граф з 7 вершинами, є ядром.

Два графи $G$ і $H$ гомоморфно еквівалентні, якщо $G\to H$ і $H\to G$.

Ретракція — це гомоморфізм r з графу $G$ в підграф $H$ графу $G$, такий, що $r(v)=v$ для кожної вершини $v$ з $H$. У цьому випадку підграф $H$ називається ретрактом графу $G$.

Ядро — це граф, який не має гомоморфізму в будь-який власний підграф. Еквівалентно, ядро можна визначити як граф, який не є ретрактом для будь-якого власного підграфу. Будь-який граф $G$ гомоморфно еквівалентний єдиному ядру (з точністю до ізоморфізму), яке називають ядром графу $G$. Зауважимо, що це не так для нескінченних графів загального вигляду. Однак ті ж визначення застосовні і до орієнтованих графів і орієнтований граф також еквівалентний єдиному ядру. Будь-який неорієнтований і орієнтований граф містить своє ядро і як ретракт, і як породжений підграф.

Наприклад, усі повні графи $K_{n}$ і всі непарні цикли (циклічні графи непарної довжини) є ядрами. Будь-який 3-розфарбовуваний граф $G$, що містить трикутник (тобто має повний граф $K_{3}$ як підграф) гомеоморфно еквівалентний $K_{3}$. Це тому, з одного боку, що 3-розфарбування графу $G$, це те саме, що й гомоморфізм $G\to K_{3}$, як пояснено нижче. З іншого боку, будь-який підграф графу $G$ тривіально допускає гомоморфізм у $G$, звідки випливає, що $K_{3}\to G$. Це також означає, що $K_{3}$ є ядром будь-якого такого графу $G$.'Аналогічно, будь-який двочастковий граф, який має принаймні одне ребро, еквівалентний $K_{2}$.

Зв'язок з розфарбуваннями

$k$-розфарбування для деякого цілого $k$ — це призначення одного з $k$ кольорів кожній вершині графу $G$ так, що кінцеві вершини кожного ребра мають різні кольори. $k$-розфарбування графу $G$ відповідають точно гомоморфізмам з $G$ в повний граф $K_{k}$. Більш того, вершини графу $K_{k}$ відповідають $k$ кольорам і два кольори суміжні як вершини графу $K_{k}$ тоді і тільки тоді, коли вони різні. Отже, функція визначає гомоморфізм у $K_{k}$ тоді і тільки тоді, коли суміжні вершини графу $G$ пофарбовано в різні кольори. Зокрема, граф $G$ $k$-розфарбовуваний тоді і тільки тоді, коли $K_{k}$-розфарбовуваний.

Якщо є два гомоморфізми $G\to H$ і $H\to K_{k}$, то їх суперпозиція $G\to K_{k}$ є також гомоморфізмом. Іншими словами, якщо граф $H$ можна розфарбувати в $k$ кольорів і існує гомоморфізм $G$ в $H$, то $G$ можна також розфарбувати в $k$ кольорів. Тому з $G\to H$ випливає $\chi (G)\leqslant \chi (H)$, де $\chi$ означає хроматичне число графу (найменше число кольорів $k$, в які можна розфарбувати граф).

Варіанти

Гомоморфізми загального вигляду можна розглядати також як вид розфарбування — якщо вершини фіксованого графу $H$ є допустимими кольорами, а ребра графу $H$ описують, які кольори сумісні, то $H$-розмальовка графу $G$ — це призначення кольорів вершин графу $G$ так, що суміжні вершини отримують сумісні кольори. Багато понять розфарбовування графів уміщуються в цю схему і можуть бути виражені як гомоморфізм графів у різні сімейства графів. Циклові розфарбування можна визначити за допомогою гомоморфізмів у циклові повні графи, уточнюючи звичайне поняття розфарбування. Дробове і b-разове розфарбування можна визначити за допомогою гомоморфізмів у кнезерівські графи. T-розфарбування відповідають гомоморфізмам у деякі нескінченні графи. Орієнтоване розфарбування орієнтованого графу є гомоморфізмом у будь-який орієнтований граф. L(2,1)-розфарбування — це локально ін'єктивний гомоморфізм у доповнення шляху, що означає, що він має бути ін'єктивним в околі кожної вершини.

Орієнтації без довгих шляхів

Інший цікавий зв'язок стосується орієнтації графів. Орієнтація неорієнтованого графу $G$ — це будь-який орієнтований граф, отриманий вибором із двох можливих орієнтацій кожного ребра. Прикладом орієнтації повного графу $K_{k}$ є транзитивний турнір ${\vec {T}}_{k}$ з вершинами 1,2, …, $k$ і дугами з i в j, коли i < j. Гомоморфізм між орієнтаціями графів $G$ і $H$ дає гомоморфізм між неорієнтованими графами $G$ і $H$, якщо просто нехтувати орієнтації. З іншого боку, якщо дано гомоморфізм $G\to H$ між неорієнтованими графами, будь-яку орієнтацію ${\vec {H}}$ з $H$ можна відобразити в орієнтацію графу ${\vec {G}}$ з $G$, так що ${\vec {G}}$ має гомоморфізм у ${\vec {H}}$. Тому граф $G$ $k$-розфарбовуваний (має гомоморфізм у $K_{k}$) тоді і тільки тоді, коли деяка орієнтація $G$ має гомоморфізм у ${\vec {T}}_{k}$.

Фольклорна теорема свідчить, що для будь-яких $k$ орієнтований граф $G$ має гомоморфізм у ${\vec {T}}_{k}$ тоді і тільки тоді, коли він не допускає гомоморфізму з ${\vec {P}}_{k+1}$. Тут ${\vec {P}}_{n}$ — орієнтований шлях з вершинами 1, 2, …, $n$ і дугами з i в i + 1 для i = 1, 2, …, $n$ — 1. Таким чином, граф $k$-розфарбовуваний тоді і тільки тоді, коли він має орієнтацію, яка не допускає гомоморфізму з ${\vec {P}}_{k+1}$. Це твердження можна злегка посилити до твердження, що граф $k$-розфарбовуваний тоді і тільки тоді, коли деяка орієнтація не містить орієнтованого шляху довжини $k$ (немає ${\vec {P}}_{k+1}$ як підграфу). Це теорема Галлаї - Хассе - Роя - Вітавера.

Зв'язок з задачами задоволення обмежень

Приклади

Граф $H$ несусідніх днів тижня ізоморфний доповненню графу $C_{7}$ і в цикловій кліці $K_{7}/2$

Деякі задачі розкладів можна промоделювати як питання про знаходження гомоморфізмів графу. Як приклад, можна спробувати призначити практичні заняття так, щоб два курси, відвідувані тим самим студентом, не були в часі занадто близькими. Курси утворюють граф $G$, з ребрами між двома курсами, якщо їх відвідує один і той самий студент. Можливий час проведення курсів утворює граф $H$ з ребрами між двома часовими вікнами, якщо відстань за часом між ними досить велика. Наприклад, якщо потрібно мати циклічний щотижневий розклад, такий, що кожен студент приходить на практичні заняття через день, то граф $H$ має бути доповненням графу $C_{7}$. Гомоморфізм графу з $G$ в $H$ є тоді призначенням курсів за часовими вікнами. Щоб додати вимогу, скажімо, щоб жоден студент не мав заняття як у п'ятницю, так і в понеділок, досить видалити одне ребро з графу $H$.

Просту задачу розподілу частот можна поставити в такий спосіб. Є кілька передавачів бездротової мережі. Потрібно вибрати на кожному з них частотний канал, яким він буде передавати дані. Щоб уникнути завад, географічно близькі передавачі повинні мати канали з достатньо відмінними частотами. Якщо цю умову обмежено простим порогом для понятть «географічно близькі» і «достатньо далекі», допустимий вибір каналів відповідає знову гомоморфізму графу. Тут графом $G$ буде набір передавачів з ребрами між ними, якщо вони географічно близькі, а графом $H$ буде набір каналів з ребрами між каналами, якщо частоти мало відрізняються. Хоча ця модель дуже спрощена, вона допускає деяку гнучкість — для пари передавачів, які не близькі, але можуть заважати один одному через географічні особливості, можна додати дугу в $G$. А дугу між передавачами, які не працюють одночасно, можна з графу видалити. Аналогічно, ребро між парою каналів, які далеко один від одного, але мають завади у вигляді гармонік можна видалити з графу $H$.

У кожному випадку ці спрощені моделі показують багато особливостей, які слід відпрацьовувати на практиці. Задачі виконання обмежень, які узагальнюють задачі гомоморфізму графу, можуть встановлювати додаткові типи умов (такі як індивідуальні переваги або обмеження на число призначень, що збігаються). Це дозволяє зробити моделі реалістичнішими і практичнішими.

Формальна точка зору

Неорієнтовані й орієнтовані графи можна розглядати як часті випадки загальнішого поняття — реляційні структури (які визначаються як множина з кортежем відношень на ньому). Орієнтовані графи є структурами з одним бінарним відношенням (суміжність) на області (множині вершин). З цієї точки зору гомоморфізми таких структур є точно гомоморфізмами графів. У загальному випадку питання пошуку гомоморфізму з однієї структури в іншу є задачею виконання обмежень. Випадок графів дає конкретний перший крок, який допомагає зрозуміти складніші задачі виконання обмежень. Багато алгоритмічних методів пошуку гомоморфізмів графу, на зразок пошуку з вертанням, поширення обмежень і локального пошуку застосовні до всіх задач виконання обмежень.

Для графів $G$ і $H$ питання, чи має граф $G$ гомоморфізм у граф $H$, відповідає окремому випадку задачі виконання обмежень з одним видом обмежень. У цій задачі змінними будуть вершини графу $G$, а областю значень кожної змінної буде набір вершин графу $H$. Розв'язком є функція, яка призначає кожній змінній елемент з області значень, так що функція f відображає $V(G)$ у $V(G)$. Кожне ребро або дуга $(u,v)$ графу $G$ тоді відповідає обмеженню $((u,v),E(H))$. Це обмеження означає, що розв'язок має відображати дугу $(u,v)$ в пару $(f(u),f(v))$, яка є відношенням $E(H)$, тобто, в дугу графу $H$. Розв'язком задачі є розв'язок, який задовольняє всім обмеженням, тобто це в точно гомоморфізм з $G$ в $H$.

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

Суперпозиції гомоморфізмів є гомоморфізмами. Зокрема, відношення $\to$ на графах транзитивне (і, тривіально, рефлексивне), так що це відношення є передпорядком на графах. Будемо позначати клас еквівалентності графу $G$ за гомоморфізмом через $[G]$. Клас еквівалентності можожна подати єдиним ядром у $[G]$. Відношення $\to$ частково впорядковане на цих класах еквівалентності. Воно визначає частково впорядковану множину.

Нехай $G<H$ означає, що існує гомоморфізм з $G$ в $H$, але немає гомоморфізму з $H$ у $G$. Відношення $\to$ є щільним порядком, це означає, що для всіх (неорієнтованих) графів $G$, $H$ таких, що $G<H$, існує граф $K$, такий, що $G<H$ (це виконується у всіх випадках, за винятком тривіальних випадків $G=K_{0}$ або $K_{1}$). Наприклад, між будь-якими двома повними графами (за винятком $K_{0},K_{1}$) є нескінченно багато циклових повних графів, відповідних раціональним числам.

Частково впорядкована множина класів еквівалентності графів за гомоморфізмом є дистрибутивною ґраткою, з об'єднанням $[G]$ і $[H]$, визначеним як (клас еквівалентності) диз'юнктне об'єднання $[G\cup H]$, і перетином $[G]$ і $[H]$ визначеним як тензорний добуток $[G\times H]$ (вибір графів $G$ і $H$ як представників класів еквівалентності $[G]$ і $[H]$ не має значення). Незвідні в об'єднанні елементи цієї ґратки — це точно зв'язні графи. Це можна показати, використовуючи факт, що гомоморфізм відображає зв'язний граф у зв'язну компоненту цільового графу. Незвідні в перетині елементи цієї ґратки — це точно мультиплікативні графи. Це графи $K$, такі, що добуток $G\times H$ має гомоморфізм у $K$ тільки тоді, коли один із графів $G$ або $H$ має такий гомоморфізм. Виявлення мультиплікативних графів є серцевиною гіпотези Гедетніємі.

Гомоморфізми графів утворюють також категорію з графами як об'єкти і гомоморфізмами як стрілками. Початковим об'єктом є порожній граф, тоді як термінальним об'єктом є граф із однією вершиною і однією петлею в цій вершині. Тензорний добуток графів є добутком у теорії категорій і експоненційний граф є експоненційним об'єктом для категорії. Оскільки ці дві операції завжди визначені, категорія графів є декартово замкнутою категорією. З тієї ж причини ґратка класів еквівалентності графів за гомоморфізмами, фактично, є алгеброю Гейтинга.

Для орієнтованих графів застосовуються ті самі визначення. Зокрема, $\to$ частково впорядковане на класах еквівалентності орієнтованих графів. Цей порядок відрізняється від порядку $\to$ на класах еквівалентності неорієнтованих графів, але містить його в як підпорядок. Це тому, що будь-який неорієнтований граф можна розглядати як орієнтований, в якому будь-яка дуга $(u,v)$ з'являється разом зі зворотною дугою $(v,u)$, а це не змінює визначення гомоморфізму. Порядок $\to$ для орієнтованих графів знову є дистрибутивною ґраткою і алгеброю Гейтинга з операціями об'єднання і перетину, визначених як раніше. Однак цей порядок не щільний. Існує також категорія з орієнтованими графами як об'єктами і гомоморфізмами як стрілками, яка також є декартово замкнутою категорією.

Непорівнянні графи

Граф Греча непорівнянний з трикутником $K_{3}$

Є багато непорівнянних графів за предпорядком гомоморфізмів, тобто пари графів, таких, що немає гомоморфізмів з одного в інший. Один зі шляхів побудови таких графів — розгляд непарного обхвату графу $G$, тобто довжини його найкоротшого циклу непарної довжини. Непарний обхват, еквівалентно, є найменшим непарним числом $g$, для якого існує гомоморфізм з графу-циклу з $g$ вершинами в $G$. З цієї причини, якщо $G\to H$, То непарний обхват графу $G$ більший або дорівнює непарному обхвату графу $H$.

З іншого боку, якщо $G\to H$, То хроматичне число графу $G$ менше або дорівнює хроматичному числу графу $H$. Тому, якщо граф $G$ має строго більший непарний обхват, ніж $H$ і строго більше хроматичне число, ніж $H$, то $G$ і $H$ непорівнянні. Наприклад, граф Греча є 4-хроматичним (розфарбовується в 4 кольори) і вільним від трикутників (він має обхват 4 і непарний обхват 5), так що він несумісний з трикутником $K_{3}$.

Прикладами графів з довільно великими значеннями непарного обхвату і хроматичного числа є кнезерові графи й узагальнені мичельськіани. Послідовність таких графів з одночасним збільшенням значень обох параметрів дає нескінченне число непорівнянних графів (антиланцюг у предпорядку гомоморфізмів). Інші властивості, такі як щільність передпорядку гомоморфізмів, можна довести за допомогою таких родин. Побудови графів з більшими значеннями хроматичного числа і обхвату, а не просто непарного обхвату, також можливі, але складніші (див. Обхват і розфарбування графів).

Серед орієнтованих графів знайти непорівнянні пари значно простіше. Наприклад, розглянемо орієнтовані графи-цикли ${\vec {C}}_{n}$ з вершинами 1, 2, …, $n$ і ребрами з i в i + 1 (для i = 1, 2, …, $n$ — 1) і з $n$ в 1. Існує гомоморфізм із ${\vec {C}}_{n}$ в ${\vec {C}}_{k}(n,k\geqslant 3)$ тоді і тільки тоді, коли $n$ кратне $k$. Зокрема орієнтовані графи-цикли ${\vec {C}}_{n}$ з простими $n$ усі непорівнянні.

Обчислювальна складність

У задачі про гомоморфізм графу примірник задачі складається з пари графів ($G$, $H$), а розв'язком є гомоморфізм із $G$ в $H$. Загальна задача розв'язності, яка питає, чи має ця задача розв'язок, NP-повна. Однак обмеження на графи дають низку різних задач, деякі з яких розв'язати легше. Методи, які використовують обмеження на лівий граф $G$, дуже відрізняються від методів, що використовуються на правий граф $H$, але в кожному разі дихотомія (строгі межі між простими і складними випадками) відома або передбачається.

Гомоморфізми у фіксований граф

Задача про гомоморфізм із фіксованим графом $H$ з правого боку кожного примірника називається задачею $H$-розфарбування. Коли $H$ є повним графом $K_{k}$, це задача $k$-розфарбовування графу, яка розв'язна за поліноміальний час для $k$ = 0, 1, 2 і NP-повна в інших випадках. Зокрема, можливість $K_{2}$-розфарбування графу $G$ еквівалентна двочастковості графу $G$, що можна перевірити за лінійний час. Загальніше, коли $H$ є двочастковим графом, можливість $H$-розфарбування еквівалентна можливості $K_{2}$-розфарбування (або $K_{0}$ / $K_{1}$-розфарбовуваності, коли $H$ порожнє або не має ребер), а отже, так само легко розв'язується. Павол Хелл і Ярослав Нешетріл довели, що для неорієнтованих графів ніякий інший випадок не є легким:

Теорема Гелла — Нешетріла (1990): Задача $H$-розфарбовування належить класу P, якщо $H$ двочастковий і NP-складна в іншому випадку.

Теорема відома також як теорема про дихотомію для гомоморфізму (неорієнтованого) графу, оскільки вона ділить задачі $H$-розфарбовування на NP-повні і задачі класу P без проміжних випадків. Для орієнтованих графів ситуація складніша і, фактично, еквівалентна загальнішому питанню опису складності дотримання обмежень. Виявляється, що задачі $H$-розфарбовування для орієнтованих графів настільки ж загальні і настільки ж різноманітні, як і задачі дотримання обмежень з будь-якими іншими видами обмежень. Формально, (скінченна) мова обмежень $\Gamma$ є скінченною областю і скінченним набором відношень у цій області. $CSP(\Gamma )$ є задачею дотримання обмежень, де примірникам дозволяється використання тільки обмежень з $\Gamma$.

Теорема (Федер, Варді 1998): Для будь-якої мови обмежень $\Gamma$ задача $CSP(\Gamma )$ еквівалентна після поліноміального зведення деякій задачі $H$-розфарбовування для деякого орієнтованого графу $H$.

Інтуїтивно це означає, що будь-яка алгоритмічна техніка або результат про складність, застосовні до задач $H$-розфарбовування для орієнтованих графів $H$, застосовні також і для загальних задач дотримання обмежень. Зокрема, можна запитати, чи можна теорему Гелла — Нешетріла поширити на орієнтовані графи. За теоремою вище це еквівалентно гіпотезі Федера — Варді про дихотомію задач дотримання обмежень, яка стверджує, що для будь-якої мови обмежень $\Gamma$ задача $CSP(\Gamma )$ або NP-повна, або належить до класу P.

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

Задачу про гомоморфізм з одним фіксованим графом $G$ ліворуч можна розв'язати повним перебором за час |V($H$)|^O(|V($G$)|), тобто поліноміально від розміру вхідного графу $H$. Іншими словами, задача тривіальна в P для графів $G$ обмеженого розміру. Цікаве питання по те, які інші властивості графу $G$, крім розміру, уможливлюють поліноміальні алгоритми.

Ключовою властивістю виявляється деревна ширина, міра, наскільки граф схожий на дерево. Для графу $G$ з деревною шириною, що не перевищує $k$, і графу $H$ задачу про гомоморфізм можна розв'язати за час |V($H$)|^O($k$) стандартними методами динамічного програмування. Фактично, досить припустити, що ядро графу $G$ має деревну ширину, яка не перевищує k. Це так навіть у разі, коли ядро не відоме.

Показник в алгоритмі з часом роботи |V($H$)|^O($k$) не можна знизити істотно — не існує алгоритму, який працює за час |V($H$)|^{o(tw($G$)/log tw($G$))} при істинності гіпотези про експоненційному часу (англ. exponential time hypothesis, ETH), навіть якщо вхід обмежено будь-яким класом графів необмеженої деревної ширини. ETH є недоведеним припущенням, аналогічним припущенню P ≠ NP, але більш строгим. За тих самих припущень немає інших властивостей, які можна використати для отримання алгоритмів поліноміального часу. Це формалізує теорема:

Теорема (Мартін Грое): Для обчисле́нного класу графів ${\mathcal {G}}$, задача про гомоморфізм для $(G,H)$ з $G\in {\mathcal {G}}$ належить P тоді і тільки тоді, коли графи ${\mathcal {G}}$ мають ядра обмеженої деревної ширини (в допущенні ETH).

Можна поставити питання, чи розв'язна задача з довільно високою залежністю від $G$, але з фіксованою поліноміальною залежністю від розміру графу $H$. Відповідь позитивна, якщо ми обмежимо граф $G$ класом з ядрами обмеженої деревної ширини, і негативна для всіх інших класів. Мовою параметризованої складності це твердження формально свідчить, що задача про гомоморфізм з графом ${\mathcal {G}}$, параметризована за розміром (кількістю ребер) графу $G$, показує дихотомію. Вона фіксовано-параметрично розв'язна, якщо графи в класі ${\mathcal {G}}$ мають ядра обмеженої деревної ширини, і W[1]-повна в іншому випадку.

Те ж твердження істинне для загальніших задач дотримання обмежень (або, іншими словами, для реляційних структур). Потрібно єдине припущення, що обмеження можуть залучати лиш обмежене число змінних. Параметром тоді є деревна ширина основного графу обмежень.

Див. також

• Гіпотеза Сидоренка

Література

• Welzl E. Color-families are dense // Theoret. Comput. Sci.. — 1982. — Т. 17 (4 листопада). — С. 29–41. — DOI:10.1016/0304-3975(82)90129-3.
• Pavol Hell, Jaroslav Nešetřil. On the complexity of H-coloring // JCTB. — 1990. — Т. 48, вип. 1 (4 листопада). — С. 92–110. — DOI:10.1016/0095-8956(90)90132-J.
• Gyárfás A., Jensen T., Stiebitz M. On Graphs With Strongly Independent Color-Classes // J. Graph Theory. — 2004. — Т. 46, вип. 1 (4 листопада). — С. 1–14. — DOI:10.1002/jgt.10165.

• Léonard Kwuida, Erkko Lehtonen. On the Homomorphism Order of Labeled Posets // Order. — Springer, 2011. — Т. 28, вип. 2 (4 листопада). — С. 251–265. — arXiv:0911.0200. — DOI:10.1007/s11083-010-9169-x.
• Tardif C. Hedetniemi's conjecture, 40 years later // Graph Theory Notes of New York. — 2008. — Т. 54 (4 листопада). — С. 46–57.
• Dwight D., Sauer N. Lattices arising in categorial investigations of Hedetniemi's conjecture // Discrete Math.. — 1996. — Т. 152, вип. 1—3 (4 листопада). — С. 125–139. — DOI:10.1016/0012-365X(94)00298-W.
• Dániel Marx. Can You Beat Treewidth? // Theory of Computing. — 2010. — Т. 6 (4 листопада). — С. 85–112. — DOI:10.4086/toc.2010.v006a005.
• Cygan M., Fomin F. V., Golovnev A., Kulikov A. S., Mihajlin I., Pachocki J., Socała A. Tight bounds for graph homomorphism and subgraph isomorphism. — SIAM, 2016. — ISBN 978-1-611974-33-1. — Bibcode:2015arXiv150703738F.
• Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi. Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics. — 2002. — С. 310–326. — DOI:10.1007/3-540-46135-3_21.
• Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side // J. ACM. — 2007. — Т. 54, вип. 1 (4 листопада). — DOI:10.1145/1206035.1206036.
• Tomás Feder, Moshe Y. Vardi. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory // SIAM J. Comput.. — 1998. — Т. 28, вип. 1 (4 листопада). — С. 57–104. — DOI:10.1137/S0097539794266766.

Книги загального характеру

• Peter Cameron. Graph Homomorphisms, Combinatorics Study Group Notes. — 2006. — 4 листопада.
• Pavol Hell, Jaroslav Nešetřil. Graphs and Homomorphisms. — Oxford University Press, 2004. — Т. 28 (4 листопада). — ISBN 0-19-852817-5.
• Geňa H., Tardif C. Graph homomorphisms: structure and symmetry // Graph Symmetry: Algebraic Methods and Applications. — Springer, 1997. — С. 107–166. — DOI:10.1007/978-94-015-8937-6_4.
• Chris Godsil, Gordon Royle. 6. Homomorphisms // Algebraic Graph Theory. — Springer–Verlag New York, 2001. — Т. 207. — (Graduate Texts in Mathematics) — ISBN 978-1-4613-0163-9. — DOI:10.1007/978-1-4613-0163-9.

В універсальній алгебрі та з урахуванням обмежень

• Bodirsky M. Graph Homomorphisms and Universal Algebra, Course Notes. — 2007. — 4 листопада.
• Pavol Hell, Jaroslav Nešetřil. Colouring, constraint satisfaction, and complexity // Computer Science Review. — 2008. — Т. 2, вип. 2 (4 листопада). — С. 143–163. — DOI:10.1016/j.cosrev.2008.10.003.

У теорії ґраток і теорії категорій

• Brown R., Morris I., Shrimpton J., Wensley C. D. Graphs of morphisms of graphs // Electronic Journal of Combinatorics. — 2008. — Т. 15, вип. 1 (4 листопада). — С. A1.
• Gray C. T. The Digraph Lattice. — 2014. — 4 листопада. (AMSI Vacation Research Scholarships, студентський звіт про дослідження під керівництвом Brian Davey і Jane Pitkethly, Університет Ла Троба).