Degree Ramsey Numbers of Graphs

Let H ->(s) 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-Delta(G; s), be min{Delta(H): H ->(s) 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-Delta(T; s) = s(k - 1) + is an element of, where is an element of = 1 when k is odd and is an element of = 0 when k is even. For general trees, R-Delta(T; s) <= 2s(Delta(T) - 1). To study sharpness of the upper bound, consider the double-star S-a,S-b, the tree whose two non-leaf vertices have degrees a and b. If a <= b, then R-Delta(S-a,S-b; 2) is 2b - 2 when a < b and b is even; it is 2b - 1 otherwise. If s is fixed and at least 3, then R-Delta(S-b,(b); s) = f(s)(b - 1) - o(b), where f(s) = 2s - 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-Delta(C2k+1; s) >= 2(s) + 1, that R-Delta(C-2k; s) >= 2s, and that R-Delta(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.