Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a
randomized algorithm which, given the ability to make queries whether
a desired pair of vertices of an input graph $G$ with $n$ vertices are
adjacent or not, distinguishes, with high probability, between the
case of $G$ satisfying $P$ and the case that it has to be modified by
adding and removing more than $\epsilon{n\choose2}$ edges to make it
satisfy $P$. The property $P$ is called testable, if for every
$\epsilon$ there exists an $\epsilon$-test for $P$ whose total number
of queries is independent of the size of the input graph. Goldreich,
Goldwasser and Ron (FOCS 1996) showed that certain graph properties,
like $k$-colorability, admit an $\epsilon$-test. In [Alon, Fischer,
Krivelevich and Szegedy, FOCS 1999] a first step towards a logical
characterization of the testable graph properties was made by proving
that properties describable by a very general type of coloring problem
are testable.

It is proven here that other classes of graph properties, describable by
various generalizations of the coloring notion used in the above article are
testable. It is also observed that these testability results, as well as
the previous results about existence of non-testable properties, can
be extended to certain combinatorial structures related to graphs, such as
tournaments.