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