We show that recognizing the $K_3$-freeness and $K_4$-freeness of
graphs is hard, respectively, for two-player nondeterministic
communication protocols with exponentially many partitions and for
nondeterministic (syntactic) read-$s$ times branching programs.
The key ingradient is a generalization of a coloring lemma, due to
Papadimitriou and Sipser, which says that for every balanced
red-blue coloring of the edges of the complete $n$-vertex graph
there is a set of $cn^2$ triangles, none of which is
monochromatic and no triangle can be formed by picking edges
from different triangles.
Using a probabilistic argument, we extend this lemma to the case
of exponentially many colorings as well as to partial colorings.
In ECCC TR01-049 we have proved a truly exponential lower bound
on the size of r-n.b.p. (nondeterministic syntacticcread-r times
branching program) recognizing whether a given graph has no
4-clique. Here we note that, although not explicitely stated there,
the same argument implies a (not truly but still exponential)
lower bound also for r-b.p.'s recognizing the triangle-freeness
of graphs.
