On the Complexity of Coloring Irreflexive Relations

Abstract

Let $\rho$ be an $h$-ary areflexive relation. We study the complexity of finding a strong $h$-coloring for $\rho$, which is defined in the same way for $h$-uniform hypergraphs.In particular we reduce the $H$-coloring problem for graphs to this problem, where $H$ is a graph depending on $\rho$. We also discuss the links of this problem with the problem of
finding a completeness criterion for finite algebras.