Grafisk homomorfism

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 oktober 2021; kontroller kräver 2 redigeringar .

En grafhomomorfism är en kartläggning mellan två grafer som inte bryter strukturen. Mer specifikt är det en mappning mellan en uppsättning hörn av två grafer som mappar intilliggande hörn till intilliggande.

Homomorphisms generaliserar olika föreställningar om graffärger och tillåter uttryck för viktiga klasser av problem med begränsningstillfredsställelse , såsom vissa schemaläggningsproblem eller problem med radiofrekvensallokering [1] . Det faktum att homomorfismer kan användas sekventiellt leder till rika algebraiska strukturer - förbeställning på grafer, distributivt gitter och kategorier (en för oriktade grafer och en för riktade grafer) [2] . Den beräkningsmässiga komplexiteten för att hitta en homomorfism mellan givna grafer är i allmänhet oöverkomlig, men många speciella fall är kända när uppgiften är genomförbar i polynomtid . Gränserna mellan lösbara och oöverstigliga fall ligger inom ett område av aktiv forskning [3] .

Definitioner

I den här artikeln, om inte annat anges, betyder grafer ändliga oriktade grafer med tillåtna loopar , men flera (parallella) kanter är inte tillåtna. En grafhomomorfism [4] [5] [6] : f från graf till graf , som skrivs som $G=(V(G),E(G))$ $H=(V(H),E(H))$

f:G\till H

är en funktion från V ( G ) till V ( H ) som mappar ändpunkterna för varje kant från G till ändpunkterna för någon kant från H. Formellt följer det av , för alla par av hörn u , v från V ( G ). Om det finns någon homomorfism från G till H , så sägs grafen G vara homomorf mot grafen H , eller att den är H -färgbar . Detta kallas ofta $\{u,v\}\in E(G)$ $\{f(u),f(v)\}\in E(H)$

G\to H

Definitionen ovan sträcker sig till riktade grafer. Sedan för en homomorfism, är en båge (riktad kant) av grafen H när ( u , v ) är en båge av grafen G. $f:G\to H,(f(u),f(v))$

Det finns en injektiv homomorfism från G till H (det vill säga en karta som aldrig mappar olika hörn till en enda) om och bara om G är en subgraf av H . Om en homomorfism är en bijektion (en en-till-en överensstämmelse mellan hörn av G och H ) vars inversa funktion också är en grafhomomorfism, då är f en grafisomorfism [7] . $f:G\till H$

Täckande kartläggningar är en vanlig typ av homomorfism som återspeglar definitionen och många egenskaper hos en täckning i topologi [8] . De definieras som surjektiva homomorfismer som är lokalt bijektiva, det vill säga en bijektion i närheten av varje vertex. Ett exempel är en dubbel täckning av en tvådelad graf bildad av en graf genom att dela upp varje vertex v i och och ersätta varje kant u , v med två kanter och . Funktionsavbildningen v 0 och v 1 till v i den ursprungliga grafen är en homomorfism och en täckande mappning. $v_{0}$ $v_{1}$ $u_{0},v_{1}$ ${\displaystyle v_{0},u_{1))$

Grafhomeomorfism är ett separat begrepp, inte direkt relaterat till homomorfismer. Grovt sett kräver det injektivitet, men tillåter kanter att mappas till banor (snarare än bara kanter). Graph minors är fortfarande ett svagare begrepp.

Kärnor och indragningar

Två grafer G och H är homomorfiskt ekvivalenta if och [4] [5] [6] . $G\to H$ $H\to G$

En retraktion är en homomorfism r från G till en subgraf H av G så att r ( v )= v för varje vertex v av H . I detta fall kallas subgrafen H en tillbakadragning av grafen G [9] .

En kärna är en graf som inte har en homomorfism till någon riktig subgraf. På motsvarande sätt kan en kärna definieras som en graf som inte är en tillbakadragning för någon riktig subgraf [10] . Varje graf G är homomorfiskt ekvivalent med en unik kärna (upp till isomorfism), som kallas kärnan i grafen G [11] [12] . Observera att detta inte är sant för allmänna oändliga grafer [13] . Samma definitioner gäller dock för riktade grafer, och en riktad graf motsvarar också en enda kärna. Alla oriktade och riktade grafer innehåller sin kärna både som en indragning och som en genererad subgraf [9] .

Till exempel är alla kompletta grafer K n och alla udda cykler ( cykelgrafer med udda längd) kärnor. Varje 3-färgbar graf G som innehåller en triangel (det vill säga har en komplett graf K 3 som en subgraf) är homeomorft ekvivalent med K 3 . Detta beror på att å ena sidan en 3-färgning av en graf G är detsamma som en homomorfism , som förklaras nedan. Å andra sidan medger varje subgraf av G trivialt en homomorfism till G , varav det följer att . Detta betyder också att K 3 är kärnan i en sådan graf G . På liknande sätt är varje tvådelad graf som har minst en kant ekvivalent med K 2 [14] . $G\to K_{3}$ $K_{3}\to G$

Förhållande med målarbok

En k -färgning för något heltal k är tilldelningen av en av de k färgerna till varje hörn av grafen G så att ändpunkten på varje kant har olika färger. k -Färgningar av grafen G motsvarar exakt homomorfismer från G till hela grafen K k [15] [16] . Dessutommotsvarar hörnen på grafen K k k färger och två färger ligger intill varandra som hörn på grafen K k om och bara om de är olika. Därför definierar funktionen en homomorfism i K k om och endast om de angränsande hörnen på grafen G är färgade i olika färger. I synnerhet är en graf G k -färgbar om och endast om den är K k -färgbar [15] [16] .

Om det finns två homomorphisms och , då deras superposition är också en homomorphism [17] . Med andra ord, om grafen H kan färgas med k färger och det finns en homomorfism G till H , så kan G också färgas med k färger. Därför följer det av , där betyder grafens kromatiska antal (det minsta antalet färger k , där grafen kan färgläggas) [18] . $G\to H$ ${\displaystyle H\to K_{k))$ ${\displaystyle G\to K_{k))$ $G\to H$ $\chi (G)\leqslant \chi (H)$ $\chi$

Alternativ

Allmänna homomorfismer kan också betraktas som en sorts färgning - om hörn av en fast graf H är tillåtna färger , och kanterna på grafen H beskriver vilka färger som är kompatibla , så är H -färgningen av grafen G tilldelningen av färger till topparna i grafen G så att intilliggande hörn får kompatibla färger. Många föreställningar om graffärgning passar in i detta schema och kan uttryckas som grafhomomorfismer i olika graffamiljer. Cykelfärgningar kan definieras genom att använda homomorfismer för att cirkulera kompletta grafer , vilket förfinar det vanliga begreppet färgning [19] [20] . Bråk- och b - faldiga färger kan definieras med hjälp av homomorfismer till Kneser-grafer [21] [22] T-färgningar motsvarar homomorfismer till några oändliga grafer [23] . { En riktad färgning av en riktad graf är en homomorfism till vilken riktad graf som helst [24] . L(2,1)-färgningen är en lokalt injektiv homomorfism i komplementet till en bana , vilket betyder att den måste vara injektiv i en grannskap av varje vertex [25] .

Orientering utan långa vägar

Ett annat intressant samband gäller orienteringen av grafer. En orientering av en oriktad graf G är vilken riktad graf som helst som erhålls genom att välja mellan två möjliga orienteringar för varje kant. Ett exempel på orienteringen av en komplett graf K k är en transitiv turnering med hörn 1,2,..., k och bågar från i till j när i < j . En homomorfism mellan orienteringarna av graferna G och H ger en homomorfism mellan de oriktade graferna G och H om vi helt enkelt bortser från orienteringarna. Å andra sidan, givet en homomorfism mellan oriktade grafer, kan varje orientering av H mappas till en orientering av grafen för G , så att den har en homomorfism i . Därför är en graf G k -färgbar (har en homomorfism i K k ) om och endast om någon orientering av G har en homomorfism i [26] . ${\vec {T}}_{k}$ $G\to H$ ${\vec {H}}$ ${\vec {G}}$ ${\vec {G}}$ ${\vec {H}}$ ${\vec {T}}_{k}$

Folkloresatsen säger att för varje k en riktad graf G har en homomorfism i om och endast om den inte medger homomorfismen från [27] . Här är en orienterad bana med hörn 1, 2, …, n och bågar från i till i + 1 för i =1, 2, …, n − 1. Grafen är alltså k -färgbar om och endast om den har orienteringen, som inte medger en homomorfism från . Detta uttalande kan förstärkas något för att säga att en graf är k -färgbar om och endast om någon orientering inte innehåller en riktad bana med längden k (inte som en subgraf). Detta är Gallai-Hasse-Roy-Vitavers sats . ${\vec {T}}_{k}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{n}$ ${\vec {P}}_{k+1}$ ${\vec {P}}_{k+1}$

Förhållande med problem med begränsningstillfredsställelse

Exempel

Vissa schemaläggningsproblem kan modelleras som en fråga om att hitta grafhomomorfismer [15] [28] . Som ett exempel kan man försöka schemalägga övningstillfällen så att två kurser som går av samma student inte ligger för nära i tiden. Kurser bildar en graf G , med kanter mellan två kurser, om de går av samma elev. Den möjliga tiden för att genomföra kurser bildar en graf H med kanter mellan två tidsfönster, om avståndet i tid mellan dem är tillräckligt stort. Till exempel, om man vill ha ett cykliskt veckoschema så att varje elev kommer till träningen varannan dag, då skulle kolumn H vara komplementet till kolumn C 7 . En grafhomomorfism från G till H är då tilldelningen av kurser över tidsfönster [15] . För att lägga till ett krav, säg att ingen elev har en klass på både fredag och måndag, räcker det att ta bort ena kanten från grafen H .

Ett enkelt frekvensfördelningsproblem kan formuleras enligt följande. Det finns flera trådlösa nätverkssändare . Du måste på var och en av dem välja frekvenskanalen genom vilken den ska överföra data. För att undvika störningar måste geografiskt nära sändare ha kanaler med tillräckligt olika frekvenser. Om detta villkor är begränsat till en enkel tröskel för begreppen "geografiskt nära" och "tillräckligt långt borta", motsvarar det giltiga valet av kanaler återigen en grafhomomorfism. Här kommer graf G att vara en uppsättning sändare med kanter mellan sig om de är geografiskt nära, och graf H kommer att vara en uppsättning kanaler med kanter mellan kanaler om frekvenserna är tillräckligt olika. Även om denna modell är mycket förenklad tillåter den viss flexibilitet - för ett par sändare som inte är nära, men som kan störa varandra på grund av geografiska egenskaper, kan en båge i G läggas till . Och bågen mellan sändare som inte fungerar samtidigt kan tas bort från grafen. På samma sätt kan en kant mellan ett par kanaler som är långt ifrån varandra men som har harmonisk interferens tas bort från H -grafen [29] .

I varje fall visar dessa förenklade modeller många funktioner som bör utarbetas i praktiken [30] . Tillfredsställelseproblem med begränsningar , som generaliserar grafhomomorfiproblem, kan uttrycka ytterligare typer av villkor (som individuella preferenser eller begränsningar av antalet matchande tilldelningar). Detta gör modellerna mer realistiska och praktiska.

Formell synvinkel

Riktade och riktade grafer kan ses som vanliga förekomster av ett mer allmänt koncept som kallas relationsstrukturer som definieras som en uppsättning med en tupel av relationer på den). Riktade grafer är strukturer med en binär relation (adjacency) på en domän (en uppsättning hörn) [31] [3] . Ur denna synvinkel är homomorfier av sådana strukturer exakt grafhomomorfismer. I det allmänna fallet är frågan om att hitta en homomorfism från en struktur till en annan ett problem med begränsningstillfredsställelse ( CSP) . Fallet med grafer ger ett konkret första steg som hjälper till att förstå mer komplexa problem med begränsningstillfredsställelse. Många algoritmiska metoder för att hitta grafhomomorfismer, som backtracking , constraint propagation , och lokal sökning är tillämpliga på alla problem med constraint satisfaction [3] .

För graferna G och H motsvarar frågan om grafen G har en homomorfism till grafen H ett särskilt fall av problemet med begränsningstillfredsställelse med endast en typ av begränsning [3] . I detta problem kommer variablerna att vara hörn i grafen G , och intervallet för varje variabel kommer att vara uppsättningen av hörn i grafen H. Lösningen är en funktion som tilldelar ett element från området till varje variabel, så att funktionen f mappar V ( G ) till V ( H ). Varje kant eller båge [32] ( u , v ) på grafen G motsvarar då begränsningen (( u , v ), E( H )). Denna begränsning uttrycker att lösningen måste avbilda bågen ( u , v ) till paret ( f ( u ), f ( v )), vilket är relationen E ( H ), d.v.s. till bågen av grafen H . Lösningen på problemet är en lösning som uppfyller alla begränsningar, det vill säga det är exakt en homomorfism från G till H .

Struktur av homomorfismer

Superpositioner av homomorfismer är homomorfismer [17] . I synnerhet är en relation på grafer transitiv (och, trivialt, reflexiv), så denna relation är en förbeställning på grafer [33] . Vi kommer att beteckna homomorfismekvivalensklassen för en graf G med [ G ]. En ekvivalensklass kan representeras av en enda kärna i [ G ]. Relationen är delvis ordnad på dessa ekvivalensklasser. Den definierar en delvis ordnad uppsättning [34] . $\till$ $\till$

Låt G < H betyda att det finns en homomorfism från G till H men ingen homomorfism från H till G . Relationen är en tät ordning , vilket betyder att för alla (oriktade) grafer G , H så att G < H , finns det en graf K så att G < K < H (detta gäller i alla fall utom för triviala fall eller ) [35] [36] [37] . Till exempel, mellan två kompletta grafer (förutom ) finns det oändligt många cykliska kompletta grafer som motsvarar rationella tal [38] [39] . $\till$ ${\displaystyle G=K_{0))$ $K_1$ ${\displaystyle K_{0},K_{1))$

En partiellt ordnad uppsättning grafekvivalensklasser genom homomorfism är ett distributivt gitter , med föreningen av [ G ] och [ H ] definierade som (ekvivalensklassen) disjunkt union och skärningspunkten mellan [ G ] och [ H ] definierade som tensorprodukt (valet av graferna G och H som representanter för ekvivalensklasserna [ G ] och [ H ] spelar ingen roll) [40] [41] . Elementen i detta gitter som är irreducerbara i unionen är exakt sammankopplade grafer. Detta kan visas med det faktum att en homomorfism mappar en sammankopplad graf till en sammankopplad komponent av målgrafen [42] [43] . De skärnings-irreducerbara elementen i detta gitter är exakt multiplikativa grafer . Dessa är grafer K så att produkten har en homomorfism i K endast om en av graferna G eller H har en sådan homomorfism. Upptäckten av multiplikativa grafer är kärnan i Hedetniemis gissningar [44] [45] . $[G\cup H]$ $[G\ gånger H]$ $G\ gånger H$

Grafhomomorfismer bildar också en kategori med grafer som objekt och homomorfismer som pilar [46] . Det initiala objektet är en tom graf, medan terminalobjektet är en graf med en vertex och en slinga vid den vertexen. Tensorprodukten av grafer är en produkt inom kategoriteorin och en exponentiell graf är ett exponentiellt objekt för en kategori [45] [47] . Eftersom dessa två operationer alltid är definierade är kategorin grafer en kartesisk sluten kategori . Av samma skäl är gittret av grafekvivalensklasser av homomorfismer i själva verket en Heyting-algebra [45] [47] .

För riktade grafer gäller samma definitioner. I synnerhet är det delvis ordnat på ekvivalensklasserna för riktade grafer. Denna ordning skiljer sig från ordningen på ekvivalensklasserna för oriktade grafer, men innehåller den som en underordning. Detta beror på att vilken oriktad graf som helst kan ses som riktad, där vilken båge som helst ( u , v ) visas tillsammans med en invers båge ( v , u ), och detta ändrar inte definitionen av en homomorfism. Ordningen för riktade grafer är återigen ett distributivt gitter och en Heyting-algebra med unions- och skärningsoperationerna definierade som tidigare. Denna ordning är dock inte snäv. Det finns också en kategori med riktade grafer som objekt och homomorfismer som pilar, vilket återigen är en kartesisk sluten kategori [48] [47] . $\till$ $\till$ $\till$

Ojämförliga grafer

Det finns många ojämförliga grafer enligt förordningen av homomorfismer, det vill säga par av grafer så att det inte finns några homomorfismer från den ena till den andra [49] . Ett av sätten att konstruera sådana grafer är att beakta den udda omkretsen av grafen G , det vill säga längden på dess kortaste cykel med udda längd. En udda omkrets är på motsvarande sätt det minsta udda tal g för vilket det finns en homomorfism från en cykelgraf med g hörn till G . Av denna anledning, om , så är den udda omkretsen av grafen G större än eller lika med den udda omkretsen av grafen H [50] . $G\to H$

Å andra sidan, om , då är det kromatiska numret för grafen G mindre än eller lika med det kromatiska talet för grafen H . Därför, om en graf G har en strikt större udda omkrets än H och ett strikt större kromatiskt [49]ojämförbaraHochG, så ärHtal än [51] , så det är inkompatibelt med triangel K 3 . $G\to H$

Exempel på grafer med godtyckligt stora värden på udda omkrets och kromatiskt tal är Kneser-grafer [52] och generaliserade Mychelskians [53] . En sekvens av sådana grafer med en samtidig ökning av värdena för båda parametrarna ger ett oändligt antal ojämförliga grafer ( en antikedja i förordningen av homomorfismer) [54] . Andra egenskaper, såsom tätheten av förordningen av homomorfismer, kan bevisas med hjälp av sådana familjer [55] . Att bygga grafer med stora värden för kromatiskt tal och omkrets, snarare än bara udda omkrets, är också möjligt, men svårare (se Grafens omkrets och färgläggning ).

Det är mycket lättare att hitta ojämförliga par bland riktade grafer. Betrakta till exempel riktade cykelgrafer med hörn 1, 2, …, n och kanter från i till i + 1 (för i =1, 2, …, n − 1) och från n till 1. Det finns en homomorfism från till då och endast när n är en multipel av k . I synnerhet är riktade cykelgrafer med prime n alla ojämförliga [56] . ${\vec {C}}_{n}$ ${\vec {C}}_{n}$ ${\vec {C}}_{k}(n,k\geqslant 3)$ ${\vec {C}}_{n}$

Beräkningskomplexitet

I grafhomomorfismproblemet består en instans av problemet av ett par grafer ( G , H ), och lösningen är en homomorfism från G till H. Det allmänna lösbarhetsproblemet , som frågar om det finns en lösning på detta problem, är NP-komplett [57] . Emellertid leder grafbegränsningar till ett antal olika problem, varav några är lättare att lösa. Metoderna som använder restriktioner på den vänstra grafen G skiljer sig mycket från metoderna som används på den högra grafen H , men i varje fall är dikotomi (strikta gränser mellan enkla och komplexa fall) känd eller antagen.

Homomorfismer till en fast graf

Homomorfismproblemet med en fast graf H på höger sida av varje instans kallas H -färgningsproblemet. När H är en komplett graf K k , är detta ett graf k - färgningsproblem som är lösbart i polynomtid för k =0, 1, 2 och är NP-komplett i övrigt [58] . I synnerhet är möjligheten för en K2 - färgning av en graf G ekvivalent med den tvådelade grafen G , som kan verifieras i linjär tid. Mer generellt, när H är en tvådelad graf, är möjligheten för H -färgning ekvivalent med möjligheten för K 2 -färgning (eller K 0 / K 1 -färgbar när H är tom eller har inga kanter), och därför lika lätt att lösa [59] . Pavol Hell och Jaroslav Neshetril bevisade att inget annat fall är lätt för oriktade grafer:

Hell-Neshetril theorem (1990): Ett H -färgningsproblem är i klass P om H är tvådelat och NP-hårt annars [60] [61] .

Satsen är också känd som dikotomisatsen för den (oriktade) grafhomomorfismen, eftersom den delar upp H -färgningsproblem i NP-kompletta och klass P-problem utan mellanliggande fall. För riktade grafer är situationen mer komplicerad och motsvarar i själva verket den mer allmänna frågan om att beskriva komplexiteten i att tillfredsställa begränsningar [62] . Det visar sig att H -färgningsproblem för riktade grafer är lika generella och lika olika som problem med begränsningstillfredsställelse med alla andra typer av begränsningar [63] [64] . Formellt är ett (finit) begränsningsspråk Γ en finit domän och en finit uppsättning relationer i den domänen. CSP( Γ ) är ett problem med begränsningstillfredsställelse där instanser endast får använda begränsningar från Γ .

Teorem (Feder, Vardy 1998): För alla begränsningsspråk Γ , är CSP( Γ ) ekvivalent efter polynomreduktion med något H -färgningsproblem för någon riktad graf H [64] .

Intuitivt betyder detta att varje algoritmisk teknik eller komplexitetsresultat som är tillämpligt på H -färgningsproblem för riktade grafer H också gäller för generella problem med tillfredsställelse av begränsningar. I synnerhet kan man fråga sig om Hell-Neshetril-satsen kan utvidgas till riktade grafer. Enligt satsen ovan är detta ekvivalent med Feder-Vardi-förmodan om dikotomien av begränsningstillfredsställelseproblem, som säger att för alla begränsningsspråk Γ , är CSP( Γ ) antingen NP-komplett eller tillhör klassen P [57] .

Homomorfismer från en fast familj av grafer

Homomorfismproblemet med en fast graf G på vänster sida kan lösas genom uttömmande tidssökning | V ( H )| O(| V ( G )|) , det vill säga polynom i storleken på ingångsgrafen H [65] . Med andra ord är problemet trivialt i P för grafer G med begränsad storlek. En intressant fråga är då vilka andra egenskaper hos grafen G förutom storlek som gör polynomalgoritmer möjliga.

Nyckelegenskapen visar sig vara treewidth , ett mått på hur lik en graf är ett träd. För en graf G med högst trädbredd k och en graf H kan homomorfismproblemet lösas i tid | V ( H )| O( k ) genom dynamiska standardprogrammeringsmetoder . Faktum är att det räcker att anta att kärnan i G har trädbredd som mest k . Detta gäller även om kärnan inte är känd [66] [67] .

Indikator i algoritmen med gångtid| V ( H )| O( k ) kan inte reduceras nämnvärt - det finns ingen algoritm som går i tid | V ( H )| o(tw( G ) /log tw( G )) om den exponentiella tidshypotesen ( ETH) är sann, även om inmatningen begränsas av någon klass av grafer med obegränsad trädbredd [68] . ETH är ett obevisat antagande, liknande P ≠ NP- antagandet , men strängare. Under samma antaganden finns det inga andra egenskaper som kan användas för att härleda polynomtidsalgoritmer. Detta formaliseras av teoremet:

Teorem (Martin Grohe): För en beräkningsbar klass av grafer tillhör homomorfismproblemet för c P om och endast om graferna har kärnor med avgränsad trädbredd (i ETH-antagandet) [67] .

{\mathcal {G}}

(G,H)

G\in {\mathcal {G}}

{\mathcal {G}}

Man kan fråga sig om problemet är lösbart med ett godtyckligt högt beroende av G , men med ett fast polynomberoende av storleken på grafen H. Svaret är ja om vi begränsar grafen G till en klass med kärnor med avgränsad trädbredd, och nej för alla andra klasser [67] . På språket av parametriserad komplexitet, säger detta uttalande formellt att homomorfismproblemet med graf , parametriserat av storleken (antal kanter) av G , visar en dikotomi. Det är avgörbart med fasta parametrar om graferna i klassen har kärnor med avgränsad trädbredd, och W[1]-komplett annars. ${\mathcal {G}}$ ${\mathcal {G}}$

Samma påstående gäller för mer generella problem med tillfredsställelse av begränsningar (eller, med andra ord, för relationsstrukturer). Det enda antagandet som krävs är att begränsningar endast kan involvera ett begränsat antal variabler. Parametern är då trädbredden för huvudbegränsningsgrafen [68] .

Se även

Hypotes Sidorenko

Anteckningar

↑ Hell, Nešetřil, 2004 , sid. 27.
↑ Hell, Nešetřil, 2004 , sid. 109.
↑ 1 2 3 4 Hell, Nešetřil, 2008 .
↑ 12 Cameron , 2006 .
↑ 1 2 Geňa, Tardif, 1997 .
↑ 1 2 Hell, Nešetřil, 2004 .
↑ Gena, Tardif, 1997 , observation 2.3.
↑ Godsil, Royle, 2001 , sid. 115.
↑ 1 2 Hell, Nešetřil, 2004 , sid. 19.
↑ Hell, Nešetřil, 2004 , Proposition 1.31.
↑ Cameron, 2006 , Proposition 2.3.
↑ Hell, Nešetřil, 2004 , Corollary 1.32.
↑ Hell, Nešetřil, 2004 , sid. 34.
↑ Cameron, 2006 , sid. 4 (Proposition 2.5).
↑ 1 2 3 4 Cameron, 2006 , sid. ett.
↑ 1 2 Hell, Nešetřil, 2004 , Proposition 1.7.
↑ 1 2 Hell, Nešetřil, 2004 , §1.7.
↑ Hell, Nešetřil, 2004 , följd 1.8.
↑ Hell, Nešetřil, 2004 , §6.1.
↑ Gena, Tardif, 1997 , §4.4.
↑ Hell, Nešetřil, 2004 , §6.2.
↑ Gena, Tardif, 1997 , §4.5.
↑ Hell, Nešetřil, 2004 , §6.3.
↑ Hell, Nešetřil, 2004 , §6.4.
↑ * Fiala J., Kratochvíl J. Partial covers of graphs // Discussions Mathematicae Graph Theory. - 2002. - T. 22 , nr. 1 . — S. 89–99 . - doi : 10.7151/dmgt.1159 .
↑ Hell, Nešetřil, 2004 , sid. 13–14.
↑ Hell, Nešetřil, 2004 , Proposition 1.20.
↑ Hell, Nešetřil, 2004 , §1.8.
↑ Hell, Nešetřil, 2004 , sid. 30–31.
↑ Hell, Nešetřil, 2004 , sid. 31–32.
↑ Hell, Nešetřil, 2004 , sid. 28. Observera att relationsstrukturer i artikeln kallas för relationssystem .
↑ Minns att kanterna på en riktad graf vanligtvis kallas bågar.
↑ Hell, Nešetřil, 2004 , §3.1.
↑ Hell, Nešetřil, 2004 , sats 3.1.
↑ Hell, Nešetřil, 2004 , sats 3.30.
↑ Geňa, Tardif, 1997 , sats 2.33.
↑ Welzl, 1982 , sid. 29–41.
↑ Hell, Nešetřil, 2004 , sid. 192.
↑ Gena, Tardif, 1997 , sid. 127.
↑ Hell, Nešetřil, 2004 , Proposition 3.2, fördelningsgrad anges i Proposition 2.4.
↑ Geňa, Tardif, 1997 , sats 2.37.
↑ Kwuida, Lehtonen, 2011 , sid. 251–265.
↑ Grey, 2014 , Lemma 3.7.
↑ Tardif, 2008 , sid. 46–57.
↑ 1 2 3 Dwight, Sauer, 1996 , sid. 125–139.
↑ Hell, Nešetřil, 2004 , sid. 125.
↑ 1 2 3 Grey, 2014 .
↑ Brown, Morris, Shrimpton, Wensley, 2008 .
↑ 1 2 Hell, Nešetřil, 2004 , sid. 7.
↑ Gena, Tardif, 1997 , observation 2.6.
↑ Weisstein, Eric W. Grötzsch Graf på Wolfram MathWorld- webbplatsen .
↑ Gena, Tardif, 1997 , Proposition 3.14.
↑ Gyárfás, Jensen, Stiebitz, 2004 , sid. 1–14.
↑ Hell, Nešetřil, 2004 , Proposition 3.4.
↑ Hell, Nešetřil, 2004 , sid. 96.
↑ Hell, Nešetřil, 2004 , sid. 35.
↑ 1 2 Bodirsky, 2007 , §1.3.
↑ Hell, Nešetřil, 2004 , §5.1.
↑ Hell, Nešetřil, 2004 , Proposition 5.1.
↑ Hell, Nešetřil, 2004 , §5.2.
↑ Hell, Nešetřil, 1990 , sid. 92–110.
↑ Hell, Nešetřil, 2004 , §5.3.
↑ Hell, Nešetřil, 2004 , sats 5.14.
↑ 1 2 Feder, Vardi, 1998 , sid. 57–104.
↑ Cygan, Fomin, Golovnev et al., 2016 , sid. 1643–1649
↑ Dalmau, Kolaitis, Vardi, 2002 , sid. 310–326.
↑ 1 2 3 Grohe, 2007 .
↑ 12 Marx , 2010 , sid. 85–112.

Litteratur

Welzl E. Färgfamiljer är täta // Teoret. Comput. sci. . - 1982. - T. 17 . — s. 29–41 . - doi : 10.1016/0304-3975(82)90129-3 .
Pavol Hell, Jaroslav Nesetzil. Om komplexiteten i H-färgning // JCTB . - 1990. - T. 48 , nr. 1 . — S. 92–110 . - doi : 10.1016/0095-8956(90)90132-J .
Gyárfás A., Jensen T., Stiebitz M. Om grafer med starkt oberoende färgklasser // J. Graph Theory . - 2004. - T. 46 , nr. 1 . — S. 1–14 . - doi : 10.1002/jgt.10165 .

Leonard Kwuida, Erkko Lehtonen. Om Homomorphism Order of Labeled Posets // Order . - Springer, 2011. - T. 28 , nr. 2 . — S. 251–265 . - doi : 10.1007/s11083-010-9169-x . - arXiv : 0911.0200 .
Tardif C. Hedetniemis gissning, 40 år senare // Graph Theory Notes of New York. - 2008. - T. 54 . — s. 46–57 .
Dwight D., Sauer N. Gitter som uppstår vid kategoriska undersökningar av Hedetniemis gissningar // Diskret matematik. . - 1996. - T. 152 , nr. 1-3 . — S. 125–139 . - doi : 10.1016/0012-365X(94)00298-W .
Daniel Marx. Kan du slå Treewidth? // Theory of Computing . - 2010. - T. 6 . — S. 85–112 . - doi : 10.4086/toc.2010.v006a005 .
Cygan M., Fomin FV, Golovnev A., Kulikov AS, Mihajlin I., Pachocki J., Socała A. Snäva gränser för grafhomomorfism och subgrafisomorfism. - SIAM , 2016. - ISBN 978-1-611974-33-1 .
Victor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi. Tillfredsställelse av begränsningar, begränsad trädbredd och logik med ändlig variabel. - 2002. - S. 310-326. - doi : 10.1007/3-540-46135-3_21 .
Martin Grohe. Komplexiteten av homomorfism och problem med tillfredsställelse av begränsningar sett från andra sidan // J. ACM . - 2007. - T. 54 , nr. 1 . - 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. - T. 28 , nr. 1 . — s. 57–104 . - doi : 10.1137/S0097539794266766 .

Allmänna böcker

Peter Cameron. Graph Homomorphisms, Combinatorics Study Group Notes . – 2006.
Pavol Hell, Jaroslav Nesetzil. Grafer och homomorfismer . - Oxford University Press, 2004. - V. 28 . — ISBN 0-19-852817-5 .
Geňa H., Tardif C. Grafhomomorfismer: struktur och symmetri // Graph Symmetry: Algebraic Methods and Applications . - Springer, 1997. - S. 107-166. - doi : 10.1007/978-94-015-8937-6_4 .
Chris Godsil, Gordon Royle. 6. Homomorfismer // Algebraisk grafteori. - Springer-Verlag New York, 2001. - T. 207. - (Graduate Texts in Mathematics). — ISBN 978-1-4613-0163-9 . - doi : 10.1007/978-1-4613-0163-9 .

I universell algebra och föremål för begränsningar

Bodirsky M. Graph Homomorphisms and Universal Algebra, Kursanteckningar . – 2007.
Pavol Hell, Jaroslav Nesetzil. Färgläggning, begränsningstillfredsställelse och komplexitet // Datavetenskaplig granskning. - 2008. - Vol. 2 , nummer. 2 . — S. 143–163 . - doi : 10.1016/j.cosrev.2008.10.003 .

I gitterteori och kategoriteori

Brown R., Morris I., Shrimpton J., Wensley CD Grafer över grafers morfismer // Electronic Journal of Combinatorics . - 2008. - T. 15 , nr. 1 . - S. A1 .
Grå CT The Digraph Lattice . — 2014. ( AMSI Vacation Research Scholarships , studentforskningsrapport övervakad av Brian Davey och Jane Pitkethly, La Trobe University ).