Degree Ramsey Numbers of Graphs

Abstract

Let H G mean that every s -colouring of E ( H ) produces a monochromatic copy of G in some colour class. Let the s-colour degree Ramsey number of a graph G , written R Δ ( G ; s ), be min{Δ( H ): H G }. If T is a tree in which one vertex has degree at most k and all others have degree at most ⌈ k /2⌉, then R Δ ( T ; s ) = s ( k − 1) + ϵ, where ϵ = 1 when k is odd and ϵ = 0 when k is even. For general trees, R Δ ( T ; s ) ≤ 2 s (Δ( T ) − 1). To study sharpness of the upper bound, consider the double-star S a,b , the tree whose two non-leaf vertices have degrees a and b . If a ≤ b , then R Δ ( S a,b ; 2) is 2 b − 2 when a < b and b is even; it is 2 b − 1 otherwise. If s is fixed and at least 3, then R Δ ( S b,b ;s ) = f ( s )( b − 1) − o ( b ), where f ( s ) = 2 s − 3.5 − O ( s −1 ). We prove several results about edge-colourings of bounded-degree graphs that are related to degree Ramsey numbers of paths. Finally, for cycles we show that R Δ ( C 2 k + 1 ; s ) ≥ 2 s + 1, that R Δ ( C 2 k ; s ) ≥ 2 s , and that R Δ ( C 4 ;2) = 5. For the latter we prove the stronger statement that every graph with maximum degree at most 4 has a 2-edge-colouring such that the subgraph in each colour class has girth at least 5.