GENERALIZED RAMSEY NUMBER (GRN): Given a complete graph c03-math-0669 with its edges partially two colored (i.e., it has a function c03-math-0670), and given an integer K > 0, determine whether it is true that for any two-colored restriction c03-math-0672 of c (i.e., c03-math-0674 for all c03-math-0675 and c03-math-0676 whenever c03-math-0677), there is a monochromatic clique in G of size K.

Theorem 3.15


Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.