GENERALIZED RAMSEY NUMBER (GRN): Given a complete graphwith its edges partially two colored (i.e., it has a function
), and given an integer K > 0, determine whether it is true that for any two-colored restriction
of c (i.e.,
for all
and
whenever
), there is a monochromatic clique in G of size K.
Theorem 3.15
Proof
Get Theory of Computational Complexity, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
