Maximal partial clones determined by the areflexive relations (Q909690)

This paper studies completeness or primality for partial algebras on a finite universe \({\mathfrak k}=\{0,1,...,k-1\}\). A universal completeness criterion reduces to finding the complete list of maximal partial clones. The authors describe all these clones for \(k\geq 3\) relating them to areflexive h-ary relations admitting a strong h-colouring. For a binary relation \(\rho\), this yields two cases: (a) if \(\rho\) is symmetric (i.e. a graph), then it determines a maximal partial clone iff \(\rho\) is bipartite; (b) if \(\rho\) is asymmetric, then it determines a maximal partial clone iff \(\rho\) is a directed graph without two consecutive arcs.