期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 c n 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.
