Abstrakt
Úplně charakterizujeme situace, ve kterých je existence homomorfismu z orientovaného grafu G do alespoň jednoho z množiny H orientovaných grafů určena konečným počtem zakázaných podgrafů. Dokážeme, že tyto situace, nazývané zobecněné duality, jsou charakterizovány neexistencí homomorfismu do G z konečné množiny lesů.
Dále charakterizujeme všechny konečné maximální antiřetězce v částečném uspořádání orientovaných grafů uspořádaných relací existence homomorfismu. Ukážeme, že tyto antiřetězce odpovídají přesně zobecněným dualitám.
Nakonec ukážeme, že je NP-těžké rozhodnout, zda konečná množina orientovaných grafů tvoří maximální antiřetězec.