Colorings generated by monotone properties

Given a graph G of order n containing no C₄, color an edge e of the complement of G red if G+e contains a C₄, and blue otherwise. Among other results, we answer a question of Erdős, de la Vina, and Fajtlowicz by showing that neither the red nor the blue graph obtained need contain a large complete subgraph. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12 : 1–25, 1998