List homomorphism to irreflexive oriented trees

Min ordering of a digraph $H$ plays an important role in deciding the existence of a list homomorphism to $H$. For reflexive oriented trees $T$, there exists a concrete forbidden induced subgraph characterization to have a min ordering. For irreflexive oriented trees $T$, the existence of a min-ordering turned out to be somewhat harder, as there are many types of obstructions to its existence. In this thesis, we first review the existing results for list homomorphism problems $LHOM(H)$ for digraphs and graphs. Second, for a specific subclass of irreflexive oriented trees, we present a concrete forbidden induced subgraph characterization to have a min ordering and to have an obstruction called invertible pair ($I$-$pair$) and digraph asteroidal triple ($DAT$). Moreover, for this subclass of irreflexive oriented trees $T$, we show that if $T$ contains one of the forbidden obstructions, then the problem $LHOM(T)$ is $NP$-complete, and is polynomial otherwise. Third, we discuss general trees, and present some approaches to find the minimal forbidden obstructions in the general case.