Premium
Generalizations of a Ramsey‐theoretic result of chvátal
Author(s) -
Burr Stefan A.,
Erdös Paul
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.3190070106
Subject(s) - mathematics , combinatorics , conjecture , ramsey's theorem , graph , ramsey theory , tree (set theory) , discrete mathematics
Chvátal has shown that if T is a tree on n points then r ( K k , T ) = ( k – 1) ( n – 1) + 1, where r is the (generalized) Ramsey number. It is shown that the same result holds when T is replaced by many other graphs. Such a T is called k ‐good. The results proved all support the conjecture that any large graph that is sufficiently sparse, in the appropriate sense, is k ‐good.