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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom