Small order graph-tree Ramsey numbers
type: Item
instance of: scholarly article
title: Small order graph-tree Ramsey numbers
zbMATH Open document ID: 0661.05042
DOI: 10.1016/0012-365X(88)90200-2
published in: Discrete Mathematics
publication date: 1988-01-01T00:00:00Z
review text: In this paper, the Ramsey number r(G,T) is determined for all, but a few exceptional cases, where G is a connected graph on five or fewer vertices and T is any tree. For a graph G, let p(G) denote the number of vertices in G, s(G) the minimum number of vertices in any color class overall \(\chi\) (G)-vertex colorings, and let \(\Delta\) (G) denote the maximum degree of a vertex of G. Let \(\epsilon (a,b)=1\) when a and b are even and 0 otherwise. Let T denote a tree and let G be any graph. Let \(t_ 1\) and \(t_ 2\) be positive integers and set \(L=t_ 1K_{p(G)-1}\cup t_ 2K_{p(G)-2}\). Choose \(t_ 1\) and \(t_ 2\) such that T is not a subgraph of \(\overline{L}\) and such that p(L) is maximal. Setting \(t(G,T)=p(L)\), we define f(G,T) to be the maximum of \((\chi (G)-1)(p(T)-1)+s(G)\), \(t(G,T)+1\), and \(\Delta (G)+\Delta (T)-\epsilon (\Delta (G),\Delta (T)).\) The main result of this paper is: Theorem 1. Let G be a connected graph with at most five vertices and let \(T_ n\) be a tree on n vertices, \(n\geq 9\). Then with but a few exceptions (those listed in (i)-(iv) below) we have \(r(G,T)=f(G,T_ n).\) (i) \(r(K_ 5-2K_ 2,K(1,n-1))=2n+1\) when n is even. (ii) \(r(K_ 5-P_ 4,K(1,n-1))=2n\) when n is even. (iii) \(r(K(2,2),T_ n)=r(K(2,3)-e,T_ n)=\max \{n+1,r(K(2,2),\Delta (T_ n))\}\) (iv) There exists a constant c such that \(n+1\leq r(K(2,3),T_ n)\leq \max \{n+c,r(K(2,3),\Delta (T_ n))\}\).
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 4079465
zbMATH Keywords: Ramsey number
author: Ralph Faudree
author: Cecil Rousseau
author: R. H. Schelp
reviewed by: Jack E. Graver
MaRDI profile type: MaRDI publication profile
cites work: Ramsey Numbers for the Pair Sparse Graph-Path or Cycle
cites work: Q3688425
cites work: Goodness of trees for generalized books
cites work: On Ramsey numbers involving starlike multipartite graphs
cites work: Q4044600
cites work: Q4120601
cites work: Multipartite graph-sparse graph Ramsey numbers
cites work: Graphs with certain families of spanning trees
cites work: Q3825106
cites work: Q3926614
cites work: On the Ramsey number of trees versus graphs with large clique number
Recommended article: Q4842722
Recommended article: Q4294586
Recommended article: Ramsey numbers for trees
Recommended article: Q3825106
Recommended article: An upper bound on the Ramsey number of trees
description: scientific article; zbMATH DE number 4079465