Maximal partial clones determined by the areflexive relations

AbstractCompleteness or primality for partial algebras on a finite universe A is defined in a way similar to full algebras. A universal completeness criterion reduces to finding the complete list of maximal partial clones. To each such clone C (with one exception, in fact a non-strong maximal clone) there is an h-ary relation on A so that C consists of all partial operations ⨍ admitting ϱ as subalgebra of 〈A,⨍〉h. In this paper we determine all such ϱ that are areflexive (i.e. consist of repetition free h-tuples). These relations are described combinatorially as relations admitting a special strong coloring. For h = 2 we obtain exactly bipartite graphs and directed graphs without two consecutive arcs. For h = 3 and ϱ totally symmetric the problem of deciding whether such coloring exists is known to be NP-complete