Antivarieties and colour-families of graphs

We suggest an algebraic approach to the study of colour-families of graphs. This approach is based on the notion of a congruence of an arbitrary structure. We prove that every colour-family of graphs is a finitely generated universal Horn class and show that for every colour-family the universal theory is decidable. We study the structure of the lattice of colour-families of graphs and the lattice of antivarieties of graphs. We also consider bases of quasi-identities and bases of anti-identities for colour-families and find certain relations between the existence of bases of a special form and problems in graph theory. Received January 19, 1999; accepted in final form October 25, 1999.