__
TR00-083 | 18th September 2000 00:00
__

#### Testing graphs for colorability properties

**Abstract:**
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.