Since it is known that r(K(1,m1),T) =
For simple graphs F and G, the Ramsey number r(F,G) is the smallest integer p such that if the edges of the complete graph Kp are colored red and blue, either the red subgraph contains a copy of F or the blue subgraph contains a copy of G. If F is a graph with chromatic number \chi(F), then the chromatic surplus s(F) is the smallest number of vertices in a color class under any \chi(F)-coloring of the vertices of F.
For any connected graph G of order n \geq s(F), the Ramsey number r(F,G) satisfies the inequality
This inequality follows from coloring red or blue the edges of a complete graph on (\chi(F)-1)(n-1)+s(F)-1 vertices such that the red subgraph is isomorphic to (\chi (F)-1) Kn-1 \cup Ks(F)-1 and the blue subgraph is isomorphic to the complement. When equality occurs in (1) we say that G is F-good. The concept of F-goodness generalizes the classical simple result of Chvátal that r(Kk,Tn) =
Our purpose is to investigate the Ramsey number r(F,Tn), when Tn is a large-order tree, and in particular to determine which large trees Tn are F-good. Since \chi(F) is important in determining the value of r(F,Tn), it is natural to carefully consider the case when F =
Not all trees are K(m0,m1,...,mk)-good when each mi \geq 2 or when m0 =
for n large. However, the principal result of [Graphs Comb. 3, 1-6 (1987; Zbl 612.05046)] is that each large-order tree TN is K(1,1,m2,m3,...,mk)-good. We will generalize this last result by proving the following theorem.
Theorem: If n is sufficiently large, then
Classif.: * 05C55 Generalized Ramsey theory
Keywords: tree; multipartite graph; Ramsey number; chromatic number; chromatic surplus
Citations: Zbl 351.05120; Zbl 672.05063; Zbl 612.05046
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag
|Books||Problems||Set Theory||Combinatorics||Extremal Probl/Ramsey Th.|
|Graph Theory||Add.Number Theory||Mult.Number Theory||Analysis||Geometry|
|Probabability||Personalia||About Paul Erdös||Publication Year||Home Page|