Name
Abstract | ||
|---|---|---|
For a positive integer n and graph B , f B ( n ) is the least integer m such that any graph of order n and minimal degree m has a copy of B . It will be show that if B is a bipartite graph with parts of order k and l ( k ⩽ l ), then there exists a positive constant c , such that for any tree T n of order n and for any j (0⩽ j ⩽( k -1)), the Ramsey number r ( T n , B )⩽ n + c ·( f B ( n )) j /( k -1) if Δ( T n )⩽( n /( k - j -1))-( j +2)· f B ( n ). In particular, this implies r ( T n , B ) is bounde d above by n + o ( n ) for any tree T n (since f B ( n )= o ( n ) when B is a Bipartite graph), and by n + O (1) if the tree T n has no vertex of large degree. For special classes of bipartite graphs, such as even cycles, sharper bounds will be proved along with examples demonstrating their sharpness. Also, applications of this to the determination of Ramsey number for arbitrary graphs and trees will be discussed. |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1016/0012-365X(88)90198-7 | Discrete Mathematics |
Keywords | Field | DocType |
bipartite graph-tree,extremal theory,ramsey number,bipartite graph | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Bounded set,Bipartite graph,Ramsey's theorem,Mathematics | Journal |
Volume | Issue | ISSN |
72 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
1 | 0.43 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| P. Erdös | 1 | 1 | 0.77 |
| R. J. Faudree | 2 | 174 | 38.15 |
| C. C. Rousseau | 3 | 126 | 22.97 |
| R. H. Schelp | 4 | 609 | 112.27 |