The Ramsey number of a graph with bounded maximum degree
The Ramsey number of a graph with bounded maximum degree
复制标题
DOI：
10.1016/0095-8956(83)90037-0
复制
发表时间：
1983-06
期刊：
影响因子：
--
通讯作者：
C. Chvatál;V. Rödl;E. Szemerédi;W. T. Trotter
中科院分区：
文献类型：
--
作者：
C. Chvatál;V. Rödl;E. Szemerédi;W. T. Trotter
一个图G的Ramsey数是一个最小的数，对于这个数，当完全图的顶点的边以任意的方式用两种颜色着色时，比如说红和蓝，那么总是红子图包含G或蓝子图包含G。Erdös和S.通过证明对每个d ≥ 1，存在一个常数c，使得G是任意n个顶点的最大度图，则G的Ramsey数至多为cn，从而肯定地解决了Burr的问题。
The Ramsey number of a graphGis the least numbertfor which it is true that whenever the edges of the complete graph ontvertices are colored in an arbitrary fashion using two colors, say red and blue, then it is always the case that either the red subgraph containsGor the blue subgraph containsG. A conjecture of P. Erdös and S. Burr is settled in the affirmative by proving that for eachd≥ 1, there exists a constantcso that ifGis any graph onnvertices with maximum degreed, then the Ramsey number ofGis at mostcn.