Grafisk homomorfism

En homomorfism från blomsnarken J ₅ in i cykeldiagrammet C ₅ . Det är också en retraktion till subgrafen på de centrala fem hörnen. Således _är J5 i själva verket homomorfiskt ekvivalent med kärnan C5 _.

Inom det matematiska området grafteori är en grafhomomorfism en kartläggning mellan två grafer som respekterar deras struktur. Mer konkret är det en funktion mellan vertexuppsättningarna av två grafer som mappar intilliggande hörn till intilliggande hörn.

Homomorphisms generaliserar olika föreställningar om graffärger och tillåter uttryck av en viktig klass av problem med begränsningstillfredsställelse , såsom vissa schemaläggnings- eller frekvenstilldelningsproblem . Det faktum att homomorfismer kan sammanställas leder till rika algebraiska strukturer: en förordning på grafer, ett distributivt gitter och en kategori (en för oriktade grafer och en för riktade grafer). Den beräkningsmässiga komplexiteten för att hitta en homomorfism mellan givna grafer är oöverkomlig i allmänhet, men mycket är känt om specialfall som är lösbara i polynomtid . Gränser mellan lösta och svårlösta fall har varit ett aktivt forskningsområde.

Definitioner

I den här artikeln, om inte annat anges, är grafer ändliga, oriktade grafer med slingor tillåtna, men flera kanter (parallella kanter) är inte tillåtna. En grafhomomorfism $f$ från en graf $G=(V(G),E(G))$ till en graf $H=(V(H),E(H))$ , skrivet

f : G \to H

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

G \to H._

Ovanstående definition utvidgas till riktade grafer. Sedan, för en homomorfism f : G → H , ( f ( u ), f ( v )) är en båge (riktad kant) av H närhelst ( u , v ) är en båge av G .

Det finns en injektiv homomorfism från G till H (dvs en som aldrig mappar distinkta hörn till en vertex) om och endast om G är en subgraf av H . Om en homomorfism f : G → H ä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 .

Täckkartor är en speciell typ av homomorfismer som speglar definitionen och många egenskaper hos täckande kartor i topologi . De definieras som surjektiva homomorfismer (dvs. något avbildar till varje vertex) som också är lokalt bijektiv, det vill säga en bijektion på grannskapet till varje vertex. Ett exempel är det tvådelade dubbeltäcket , bildat av en graf genom att dela upp varje vertex v i v ₀ och v ₁ och ersätta varje kant u , v med kanterna u ₀ , v ₁ och v ₀ , u ₁ . Funktionsavbildningen v ₀ och v ₁ i omslaget till v i den ursprungliga grafen är en homomorfism och en täckande karta.

Grafhomeomorfism är en annan uppfattning , inte direkt relaterad till homomorfismer. Grovt sett kräver det injektivitet, men tillåter kartläggning av kanter till banor (inte bara till kanter). Graph minors är ett ännu mer avslappnat begrepp.

Kärnor och dras in

K ₇ , den kompletta grafen med 7 hörn, är en kärna.

Två grafer G och H är homomorfiskt ekvivalenta om G → H och H → G . Kartorna är inte nödvändigtvis surjektiva eller injektiva. Till exempel är de kompletta tvådelade graferna K _2,2 och K _3,3 homomorfiskt ekvivalenta: varje karta kan definieras som att ta den vänstra (resp. högra) halvan av domängrafen och avbilda till bara en vertex i vänster (resp. höger) . höger) hälften av bildgrafen.

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

En kärna är en graf utan homomorfism till någon riktig subgraf. På motsvarande sätt kan en kärna definieras som en graf som inte dras tillbaka till någon riktig subgraf. Varje graf G är homomorfiskt ekvivalent med en unik kärna (upp till isomorfism), kallad kärnan av G . Noterbart är detta inte sant i allmänhet för oändliga grafer. Samma definitioner gäller dock för riktade grafer och en riktad graf motsvarar också en unik kärna. Varje graf och varje riktad graf innehåller sin kärna som en indragning och som en inducerad subgraf .

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 hela grafen K ₃ som en subgraf) är homomorfiskt ekvivalent med K ₃ . Detta beror på att, å ena sidan, en 3-färgning av G är detsamma som en homomorfism G → K ₃ , som förklaras nedan. Å andra sidan erkänner varje subgraf av G trivialt en homomorfism till G , vilket antyder K ₃ → G . Detta betyder också att K ₃ ä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 ₂ .

Anslutning till färger

En k -färgning , för något heltal k , är en tilldelning av en av k färger till varje vertex i en graf G så att ändpunkterna för varje kant får olika färger. K - färgningarna av G motsvarar exakt homomorfismer från G till hela grafen K _k . I själva verket motsvarar hörnen av K _{k färgerna} k , och två färger ligger intill varandra som hörn av K _k om och bara om de är olika. Därför definierar en funktion en homomorfism till K _k om och endast om den mappar intilliggande hörn av G till olika färger (dvs. det är en k -färgning). Speciellt är G k -färgbar om och endast om den är Kk _- färgbar.

Om det finns två homomorfismer G → H och H → K _k , så är deras sammansättning G → K _k också en homomorfism. Med andra ord, om en graf H kan färgas med k färger, och det finns en homomorfism från G till H , så kan G också vara k -färgad. Därför G → H χ( G ) ≤ χ( H ), där χ anger det kromatiska talet för en graf (det minsta k för vilket det är k -färgbart).

Varianter

Allmänna homomorfismer kan också ses som en sorts färgning: om hörnen på en fast graf H är de tillgängliga färgerna och kanterna på H beskriver vilka färger som är kompatibla , så är en H -färgning av G en tilldelning av färger till hörn av G så att närliggande hörn får kompatibla färger. Många föreställningar om graffärgning passar in i detta mönster och kan uttryckas som grafhomomorfismer i olika graffamiljer. Cirkulära färger kan definieras med hjälp av homomorfismer till cirkulära kompletta grafer , vilket förfinar det vanliga begreppet färgningar. Bråk- och b -faldig färgning kan definieras med hjälp av homomorfismer till Kneser-grafer . T-färgningar motsvarar homomorfismer till vissa oändliga grafer. En orienterad färgning av en riktad graf är en homomorfism till vilken orienterad graf som helst . En L(2,1)-färgning är en homomorfism i komplementet till väggrafen som är lokalt injektiv, vilket betyder att den måste vara injektiv i närheten av varje vertex.

Inriktningar utan långa vägar

Ett annat intressant samband gäller orienteringar av grafer. En orientering av en oriktad graf G är vilken riktad graf som helst som erhålls genom att välja en av de två möjliga orienteringarna för varje kant. Ett exempel på en orientering av hela grafen K _k är den transitiva turneringen T → _k 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 , helt enkelt genom att bortse från orienteringarna. Å andra sidan, givet en homomorfism G → H mellan oriktade grafer, kan vilken orientering H → av H som helst dras tillbaka till en orientering G → av G så att G → har en homomorfism till H → . Därför är en graf G k -färgbar (har en homomorfism till K _k ) om och endast om någon orientering av G har en homomorfism till T → _k .

En folkloresats säger att för alla k har en riktad graf G en homomorfism till T → _k om och endast om den inte tillåter någon homomorfism från den riktade banan P → _{k +1} . Här P → _n den riktade grafen med hörn 1, 2, …, n och kanter från i till i + 1, för i = 1, 2, …, n − 1. Därför är en graf k -färgbar om och endast om den har en orientering som inte tillåter någon homomorfism från P → _{k +1} . 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 någon riktad bana med längden k (ingen P → _{k +1} som en subgraf). Detta är Gallai-Hasse-Roy-Vitavers sats .

Anslutning till problem med begränsningstillfredsställelse

Exempel

Diagram H för icke på varandra följande vardagar, isomorft till komplementgrafen för C ₇ och till den cirkulära klicken K _7/2

Vissa schemaläggningsproblem kan modelleras som en fråga om att hitta grafhomomorfismer. Som ett exempel kan man vilja tilldela verkstadskurser till tidsluckor i en kalender så att två kurser som går av samma student inte ligger för nära varandra i tiden. Kurserna bildar en graf G , med en kant mellan två valfria kurser som går av någon vanlig student. Tidsluckorna bildar en graf H , med en kant mellan två valfria luckor som är tillräckligt långt borta i tiden. Till exempel, om man vill ha ett cykliskt veckoschema, så att varje elev får sina workshopkurser på icke på varandra följande dagar, då H vara komplementgrafen för C ₇ . En grafhomomorfism från G till H är sedan ett schema som tilldelar banor till tidsluckor, enligt vad som anges. För att lägga till ett krav på att t.ex. ingen enskild elev har kurser på både fredag och måndag räcker det att ta bort motsvarande kant från H .

Ett enkelt frekvensallokeringsproblem kan specificeras enligt följande: ett antal sändare i ett trådlöst nätverk måste välja en frekvenskanal som de ska sända data på. För att undvika störningar bör sändare som är geografiskt nära använda kanaler med frekvenser som ligger långt ifrån varandra. Om detta tillstånd approximeras med en enda tröskel för att definiera "geografiskt nära" och "långt ifrån varandra", så motsvarar ett giltigt kanalval återigen en grafhomomorfism. Den ska gå från grafen för sändarna G , med kanter mellan par som är geografiskt nära, till grafen för kanalerna H , med kanter mellan kanaler som är långt ifrån varandra. Även om den här modellen är ganska förenklad, medger den viss flexibilitet: sändarpar som inte är nära men som kan störa på grund av geografiska särdrag kan läggas till kanterna på G . De som inte kommunicerar samtidigt kan tas bort från den. På liknande sätt kan kanalpar som är långt ifrån varandra men uppvisar harmonisk interferens tas bort från kantuppsättningen av H .

I varje fall visar dessa förenklade modeller många av de frågor som måste hanteras i praktiken. Tillfredsställelseproblem med begränsningar , som generaliserar grafhomomorfismproblem, kan uttrycka olika ytterligare typer av villkor (som individuella preferenser eller gränser för antalet sammanfallande tilldelningar). Detta gör att modellerna kan göras mer realistiska och praktiska.

Formell syn

Grafer och riktade grafer kan ses som ett specialfall av den mycket mer allmänna uppfattningen som kallas relationsstrukturer ( definierad som en uppsättning med en tupel av relationer på den). Riktade grafer är strukturer med en enda binär relation (adjacency) på domänen (vertexuppsättningen). Enligt detta synsätt homomorfismer av sådana strukturer exakt grafhomomorfismer. Generellt sett är frågan om att hitta en homomorfism från en relationsstruktur 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 komplicerade CSP:er. Många algoritmiska metoder för att hitta grafhomomorfismer, som backtracking , restriktionsförökning och lokal sökning , gäller för alla CSP:er.

För graferna G och H motsvarar frågan om G har en homomorfism till H en CSP-instans med endast en typ av begränsning, enligt följande. Variablerna är hörn av G och domänen för varje variabel är vertexuppsättningen av H . En utvärdering är en funktion som tilldelar varje variabel ett element i domänen, alltså en funktion f från V ( G ) till V ( H ). Varje kant eller båge ( u , v ) av G motsvarar då begränsningen (( u , v ), E( H )). Detta är en begränsning som uttrycker att utvärderingen ska mappa bågen ( u , v ) till ett par ( f ( u ), f ( v )) som är i relationen E ( H ), det vill säga till en båge av H . En lösning på CSP är en utvärdering som respekterar alla begränsningar, så det är exakt en homomorfism från G till H .

Struktur av homomorfismer

Sammansättningar av homomorfismer är homomorfismer. I synnerhet är relationen → på grafer transitiv (och reflexiv, trivialt), så det är en förbeställning på grafer. Låt ekvivalensklassen för en graf G under homomorf ekvivalens vara [ G ]. Ekvivalensklassen kan också representeras av den unika kärnan i [ G ]. Relationen → är en partiell ordning på dessa ekvivalensklasser; det definierar en poset .

₀₀ Låt G < H beteckna 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 förutom trivialfallen G = K eller K ₁ ). Till exempel, mellan två kompletta grafer (förutom K , K ₁ , K ₂ ) finns det oändligt många cirkulära kompletta grafer , motsvarande rationella tal mellan naturliga tal.

Poseten av ekvivalensklasser av grafer under homomorfismer är ett distributivt gitter , med sammanfogningen av [ G ] och [ H ] definierade som (ekvivalensklassen för) den disjunkta föreningen [ G ∪ H ] och mötet av [ G ] och [ H ] definierad som tensorprodukten [ G × H ] (valet av grafer G och H som representerar ekvivalensklasserna [ G ] och [ H ] spelar ingen roll). De sammanfognings-irreducerbara elementen i detta gitter är exakt sammankopplade grafer. Detta kan visas med det faktum att en homomorfism mappar en sammankopplad graf till en sammankopplad komponent av målgrafen. De möts-irreducerbara elementen i detta gitter är exakt de multiplikativa graferna . Dessa är graferna K så att en produkt G × H har en homomorfism till K endast när en av G eller H också gör det. Att identifiera multiplikativa grafer ligger i hjärtat av Hedetniemis gissningar .

Grafhomomorfismer bildar också en kategori , med grafer som objekt och homomorfismer som pilar. Det initiala objektet är den tomma grafen, medan terminalobjektet är grafen med en vertex och en slinga vid den vertexen. Tensorprodukten av grafer är den kategoriteoretiska produkten och exponentialgrafen är exponentialobjektet för denna kategori. Eftersom dessa två operationer alltid är definierade är kategorin grafer en kartesisk sluten kategori . Av samma anledning är gittret av ekvivalensklasser av grafer under homomorfismer i själva verket en Heyting-algebra .

För riktade grafer gäller samma definitioner. I synnerhet → är en partiell ordning på ekvivalensklasser av riktade grafer. Den är skild från ordningen → på ekvivalensklasser av oriktade grafer, men innehåller den som en underordning. Detta beror på att varje oriktad graf kan ses som en riktad graf där varje båge ( u , v ) visas tillsammans med sin inversa båge ( v , u ), och detta ändrar inte definitionen av homomorfism. Ordningen → för riktade grafer är återigen ett distributivt gitter och en Heyting-algebra, med join- och mötesoperationer definierade som tidigare. Det är dock inte tätt. Det finns också en kategori med riktade grafer som objekt och homomorfismer som pilar, vilket återigen är en kartesisk sluten kategori .

Ojämförliga grafer

Grötzsch-grafen, ojämförlig med K ₃

Det finns många ojämförliga grafer med avseende på homomorfismens förordnande, det vill säga par av grafer som inte medger en homomorfism i den andra. Ett sätt att konstruera dem är att betrakta den udda omkretsen av en graf G , längden på dess kortaste cykel med udda längd. Den udda omkretsen är, ekvivalent, det minsta udda tal g för vilket det finns en homomorfism från cykelgrafen på g hörn till G . Av denna anledning, om G → H , så är den udda omkretsen av G större än eller lika med den udda omkretsen av H .

Å andra sidan, om G → H , så är det kromatiska talet för G mindre än eller lika med det kromatiska talet för H . Därför, om G har en strikt större udda omkrets än H och strikt större kromatiskt tal än H , så är G och H ojämförliga. Till exempel Grötzsch-grafen 4-kromatisk och triangelfri (den har omkrets 4 och udda omkrets 5), så den är ojämförbar med triangelgrafen K ₃ .

Exempel på grafer med godtyckligt stora värden på udda omkrets och kromatiskt tal är Kneser-grafer och generaliserade mycielsker . En sekvens av sådana grafer, med samtidigt ökande värden på båda parametrarna, ger oändligt många ojämförliga grafer (en antikedja i homomorfismförordningen). Andra egenskaper, såsom tätheten av homomorfismförordningen, kan bevisas med hjälp av sådana familjer. Konstruktioner av grafer med stora värden på kromatiskt tal och omkrets, inte bara udda omkrets, är också möjliga, men mer komplicerade (se Omkrets och graffärgning ) .

Bland riktade grafer är det mycket lättare att hitta makalösa par. Betrakta till exempel de riktade cykelgraferna C → _n , 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. Där är en homomorfism från C → _n till C → _k ( n , k ≥ 3) om och endast om n är en multipel av k . Speciellt riktade cykelgrafer C → _n med n primtal är alla ojämförliga.

Beräkningskomplexitet

I grafhomomorfismproblemet är en instans ett par grafer ( G , H ) och en lösning är en homomorfism från G till H . Det allmänna beslutsproblemet , att fråga om det finns någon lösning, är NP-komplett . Att begränsa tillåtna instanser ger dock upphov till en mängd olika problem, av vilka några är mycket lättare att lösa. Metoder som gäller vid fasthållning av vänster sida G är mycket annorlunda än för höger sida H , men i varje fall är en dikotomi (en skarp gräns mellan lätta och svåra fall) känd eller gissad.

Homomorfismer till en fast graf

₀ Homomorfismproblemet med en fast graf H på höger sida av varje instans kallas också H -färgningsproblemet. När H är den fullständiga grafen K _k , är detta grafens k -färgningsproblem , som är lösbart i polynomtid för k = 0, 1, 2 och NP-komplett annars. Speciellt K2 _- färgbarheten hos en graf G ekvivalent med att G är bipartit , vilket kan testas i linjär tid. Mer generellt, närhelst H är en tvådelad graf, är H -färgbarhet ekvivalent med K ₂ -färgbarhet (eller K / K ₁ -färgbarhet när H är tom/kantlös), och därför lika lätt att avgöra. Pavol Hell och Jaroslav Nešetřil bevisade att, för oriktade grafer, inget annat fall är löst:

Hell–Nešetřils sats (1990): H- färgningsproblemet är i P när H är tvådelat och NP-komplett annars.

Detta är också känt som dikotomisatsen för (oriktade) grafhomomorfismer, eftersom den delar upp H -färgningsproblem i NP-kompletta eller P-problem, utan mellanliggande fall. För riktade grafer är situationen mer komplicerad och i själva verket likvärdig med den mycket mer allmänna frågan om att karakterisera komplexiteten i problem med tillfredsställelse av begränsningar . Det visar sig att H -färgningsproblem för riktade grafer är lika allmänna och lika olika som CSP:er med alla andra typer av begränsningar. Formellt är ett (finit) begränsningsspråk (eller mall ) Γ en ändlig domän och en ändlig uppsättning relationer över denna domän. CSP( Γ ) är problemet med begränsningstillfredsställelse där instanser endast får använda begränsningar i Γ .

Teorem (Feder, Vardi 1998): För varje begränsningsspråk Γ är problemet CSP( Γ ) likvärdigt under polynomtidsreduktioner med något H -färgningsproblem, för någon riktad graf H .

Intuitivt betyder detta att varje algoritmisk teknik eller komplexitetsresultat som gäller för H -färgningsproblem för riktade grafer H gäller lika väl för allmänna CSP:er. I synnerhet kan man fråga sig om Hell–Nešetřils sats kan utvidgas till riktade grafer. Enligt ovanstående sats är detta ekvivalent med Feder–Vardi-förmodan (aka CSP-förmodan, dikotomiförmodan) om CSP-dikotomi, som säger att för varje tvångsspråk Γ , är CSP( Γ ) NP-komplett eller i P. Denna gissning var bevisades 2017 oberoende av Dmitry Zhuk och Andrei Bulatov, vilket ledde till följande följd:

Följd (Bulatov 2017; Zhuk 2017): H -färgningsproblemet på riktade grafer, för ett fast H , är antingen i P eller NP-komplett.

Homomorfismer från en fast familj av grafer

Homomorfismproblemet med en enda fast graf G på vänster sida av ingångsinstanser kan lösas med brute-force i tid | V ( H )| ^{O(| V ( G )|)} , alltså polynom i storleken på ingångsgrafen H . Med andra ord är problemet trivialt i P för grafer G med begränsad storlek. Den intressanta frågan är då vilka andra egenskaper hos G , förutom storlek, som gör polynomalgoritmer möjliga.

Den avgörande egenskapen visar sig vara treewidth , ett mått på hur trädliknande grafen är. För en graf G med högst k trädbredd och en graf H kan homomorfismproblemet lösas i tid | V ( H )| ^{O( k )} med en standardmässig dynamisk programmeringsmetod . 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.

Exponenten i | V ( H )| ^{O( k )} -tidsalgoritmen kan inte sänkas avsevärt: ingen algoritm med körtid | V ( H )| ^{o(tw( G ) /log tw( G ))} existerar, med antagande av den exponentiella tidshypotesen (ETH), även om indata är begränsade till vilken klass av grafer som helst med obegränsad trädbredd. ETH är ett obevisat antagande som liknar P ≠ NP , men starkare. Under samma antagande finns det i princip inga andra egenskaper som kan användas för att få polynomtidsalgoritmer. Detta är formaliserat enligt följande:

Teorem ( Grohe ): För en beräkningsbar klass av grafer

{\mathcal {G}}

, homomorfismproblemet för instanser

(G,H)

med

G\in {\mathcal {G}}

är i P om och endast om grafer i

{\mathcal {G}}

har kärnor med begränsad trädbredd (förutsatt ETH).

Man kan fråga sig om problemet åtminstone är lösbart i en tid som är godtyckligt starkt beroende av G , men med ett fast polynomberoende av storleken på H . Svaret är återigen positivt om vi begränsar G till en klass av grafer med kärnor med begränsad trädbredd, och negativt för varannan klass. På språket parametriserad komplexitet anger detta formellt att homomorfismproblemet i ${\mathcal {G}}$ parametriserat av storleken (antal kanter) av G uppvisar en dikotomi. Det går att hantera med fasta parametrar om grafer i ${\mathcal {G}}$ har kärnor med begränsad trädbredd och W[1] -komplett annars.

Samma påståenden gäller mer generellt för problem med tillfredsställelse av begränsningar (eller för relationsstrukturer, med andra ord). Det enda antagandet som behövs är att begränsningar endast kan involvera ett begränsat antal variabler (alla relationer är av någon gränsad aritet, 2 i fallet med grafer). Den relevanta parametern är då trädbredden för den primära begränsningsgrafen .

Se även

Ordlista över grafteoretiska termer
Homomorphism , för samma uppfattning om olika algebraiska strukturer
Graf omskrivning
Mediangrafer , definierbara som indragningar av hyperkuber
Sidorenkos gissning

Anteckningar

Allmänna böcker och utställningar

Cameron, P. (2006), Graph Homomorphisms, Combinatorics Study Group Notes (PDF)
Helvete, Pavol ; Nešetřil, Jaroslav (2004), Graphs and Homomorphisms , Oxford Lecture Series in Mathematics and Its Applications, vol. 28, Oxford University Press, ISBN 0-19-852817-5
Hahn, G.; Tardif, C. (1997), "Graph homomorphisms: structure and symmetry", Graph Symmetry: Algebraic Methods and Applications (PDF) , Springer, s. 107–166, doi : 10.1007/978-94-015-8937-6_
Godsil, C .; Royle, G. (2001), "6. Homomorphisms", Algebraic Graph Theory , Graduate Texts in Mathematics, vol. 207, Springer–Verlag New York, doi : 10.1007/978-1-4613-0163-9 , ISBN 978-1-4613-0163-9

I tvångstillfredsställelse och universell algebra

Bodirsky, M. (2007), Graph Homomorphisms and Universal Algebra, Kursanteckningar (PDF)
Helvete, Pavol ; Nešetřil, Jaroslav (2008), "Colouring, constraint satisfaction, and complexity" (PDF) , Computer Science Review , 2 (3): 143–163, doi : 10.1016/j.cosrev.2008.10.003

I gitterteori och kategoriteori

Brown, R.; Morris, I.; Shrimpton, J.; Wensley, CD (2008), "Graphs of morphisms of graphs" , Electronic Journal of Combinatorics , 15 (1): A1, doi : 10.37236/919
Gray, CT (2014), The Digraph Lattice (PDF) ( AMSI Vacation Research Scholarships , studentforskningsrapport övervakad av Brian Davey och Jane Pitkethly, La Trobe University ).