A fundamental goal of computer science is to understand the complexity of computational problems. One class of problems are promise constraint satisfaction problems (PCSP's). We study PCSP's related to graph coloring, linearly ordered coloring (LO-coloring) and rainbow coloring. We first dive into graph coloring PCSP's and classify the non-existence of certain gadget reductions between such problems. Next we systematically classify the existence gadget reductions between PCSP's related to graph coloring and LO-coloring and between PCSP's related to graph coloring and rainbow coloring that could yield new complexity results. For the most part these gadget reductions are shown to be non-existent. We do however prove the existence of a reduction from PCSP($\K_l,\K_k$) to PCSP($\LO_l^r,\LO_k^r$) for $k\geq l\geq 3$ and $r\geq 4$ yielding a substantial number of new NP-hardness results for PCSP($\LO_l^r,\LO_k^r$).

Ett fundamentalt mål inom datalogi är att förstå komplexiteten av beräkningsproblem. En klass of dessa problem är villkorssatisfieringsproblem under löften (PCSP:er). Vi studerar PCSP:er relaterade till graffärgning, linjärt ordnad färgning (LO-färgning) och regnbågsfärgning. Vi dyker först in i graffärgings PCSP:er och klassificerar ickeexistensen av vissa mojängreduktioner mellan sådana problem. Sedan klassificerar vi systematiskt existensen av mojängreduktioner mellan PCSP:er relaterade till graffärgning och LO-färgning samt mellan PCSP:er relaterade till graffärgning och regnbågsfärgning. För det mesta visas det att dessa mojängreduktioner är ickeexisterand. Vi bevisar dock existensen av en mojängreduktion från PCSP($\K_l,\K_k$) till PCSP($\LO_l^r,\LO_k^r$) för $k\geq l\geq 3$ och $r\geq 4$ vilket ger en ansenlig mängd nya NP-svåra resultat för PCSP($\LO_l^r,\LO_k^r$).