Premium
Ramsey problems and their connection to tuŕan‐type extremal problems
Author(s) -
Faudree Ralph J.,
Simonovits Miklós
Publication year - 1992
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.3190160105
Subject(s) - ramsey's theorem , combinatorics , mathematics , graph , colored , type (biology) , edge coloring , chromatic scale , connection (principal bundle) , function (biology) , discrete mathematics , graph power , line graph , ecology , materials science , geometry , composite material , biology , evolutionary biology
We shall investigate the behavior of the Ramsey function r ( L, T n ), where L is a fixed graph and T n is a tree on n vertices, while n ← ∞. We prove that in this case the appropriate Ramsey problem can be reduced to a corresponding Turán type extremal problem: if we take a maximum N for which a K N can be colored in two colors so that the first color contains no L and the second color contains no T n , then by the results of Erdös, Faudree, Rousseau and Schelp, N = ( p ‐ 1) n + 0( n ), where p is the chromatic number of L . We shall prove that in the corresponding Ramsey‐coloring the edges of the first color from an “almost Turán graph” on p ‐ 1 classes. We shall also describe how the finer structure of L influences this Ramsey number and the stability of the Ramsey coloring. The most important new results—compared with some earlier results—are that we can guarantee structural properties of the extremal colorings.