Premium
Colorings generated by monotone properties
Author(s) -
Bollobás Béla,
Riordan Oliver
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199801)12:1<1::aid-rsa1>3.0.co;2-2
Subject(s) - monotone polygon , mathematics , combinatorics , geometry
Given a graph G of order n containing no C 4 , color an edge e of the complement of G red if G + e contains a C 4 , 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