Premium
On a Quasi‐Ramsey problem
Author(s) -
Erdös Paul,
Pach János
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070117
Subject(s) - combinatorics , mathematics , complement (music) , graph , induced subgraph , degree (music) , discrete mathematics , chemistry , physics , vertex (graph theory) , biochemistry , complementation , acoustics , gene , phenotype
It is proved that if a graph G has atleast cn log n vertices, then either G or its complement G contains a subgraph H with atleast n vertices and minimum degree atleast | V ( H )|/2. This result is not far from being best possible, as is shown by a rather unusual random construction. Some related questions are also discussed.