COLORINGS GENERATED BY MONOTONE PROPERTIES

Authors
BOLLOBAS B RIORDAN O
Citation
B. Bollobas et O. Riordan, COLORINGS GENERATED BY MONOTONE PROPERTIES, Random structures & algorithms, 12(1), 1998, pp. 1-25
Citations number
5
Categorie Soggetti
Mathematics,Mathematics,"Computer Science Software Graphycs Programming",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
12
Issue
1
Year of publication
1998
Pages
1 - 25
Database
ISI
SICI code
1042-9832(1998)12:1<1:CGBMP>2.0.ZU;2-J
Abstract
Given a graph G of order n containing no C-4, color an edge e of the c omplement of G red if G + e contains a C-4, and blue otherwise. Among other results, we answer a question of Erdos, de la Vina, and Fajtlowi cz by showing that neither the red nor the blue graph obtained need co ntain a large complete subgraph. (C) 1998 John Wiley & Sons, Inc.