Abstract. In this paper we give a characterization of the following three clones of operations on binary relations: the clone of primitive-positive Tarski operations, the clone of positive Tarski operations and the clone of all Tarski operations (or the classical clone). Operations from each of the three clones can be represented by special first-order formulas; to each such formula we assign a labelled multigraph and show that an operation belongs to the respective clone if and only if the suitably transformed graph of its formula does not contain a subgraph homeomorphic to $K_4$.

AMS Subject Classification (1991): 03G15, 08A40

Keyword(s): Tarski relation algebra, clone

Received September 16, 2003, and in final form March 31, 2004. (Registered under 5825/2009.)