z-logo
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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here