首页   按字顺浏览 期刊浏览 卷期浏览 On the Ramsey number of trees versus graphs with large clique number
On the Ramsey number of trees versus graphs with large clique number

 

作者: Ronald J. Gould,   Michael S. Jacobson,  

 

期刊: Journal of Graph Theory  (WILEY Available online 1983)
卷期: Volume 7, issue 1  

页码: 71-78

 

ISSN:0364-9024

 

年代: 1983

 

DOI:10.1002/jgt.3190070109

 

出版商: Wiley Subscription Services, Inc., A Wiley Company

 

数据来源: WILEY

 

摘要:

AbstractChvátal established thatr(Tm, Kn) = (m– 1)(n– 1) + 1, whereTmis an arbitrary tree of ordermandKnis the complete graph of ordern. This result was extended by Chartrand, Gould, and Polimeni who showedKncould be replaced by a graph with clique numbernand ordern+ 1 providedn≧ 3 andm≧ 3. We further extend these results to show thatKncan be replaced by any graph onn+ 2 vertices with clique numbern, providedn≧ 5 andm≧ 4. We then show that further extensions, in particular to graphs onn+ 3 vertices with clique numbernare impossible. We also investigate the Ramsey number of trees versus complete graphs minus sets of independent edges. We show thatr(Tm, Kn–tK2) = (m– 1)(n – t– 1) + 1 form≧ 3,n≧ 6, whereTmis any tree of ordermexcept the star, and for

 

点击下载:  PDF (334KB)



返 回