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.