## On Multi-Partition Communication Complexity of Triangle-Freeness

Stasys Jukna and Georg Schnitger

**Abstract.**
We show that recognizing the triangle-freeness and 4-clique-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.

**Key Words:** Edge colorings, expanders, triangle-free graphs,
communication complexity, branching programs, lower bounds