{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T00:52:43Z","timestamp":1722559963062},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"1-2","license":[{"start":{"date-parts":[[2012,2,2]],"date-time":"2012-02-02T00:00:00Z","timestamp":1328140800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p>Let <jats:italic>H<\/jats:italic><jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000617_char1\" \/><\/jats:private-char><jats:italic>G<\/jats:italic> mean that every <jats:italic>s<\/jats:italic>-colouring of <jats:italic>E<\/jats:italic>(<jats:italic>H<\/jats:italic>) produces a monochromatic copy of <jats:italic>G<\/jats:italic> in some colour class. Let the <jats:italic>s-colour degree Ramsey number<\/jats:italic> of a graph <jats:italic>G<\/jats:italic>, written <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>G<\/jats:italic>; <jats:italic>s<\/jats:italic>), be min{\u0394(<jats:italic>H<\/jats:italic>): <jats:italic>H<\/jats:italic><jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000617_char1\" \/><\/jats:private-char><jats:italic>G<\/jats:italic>}. If <jats:italic>T<\/jats:italic> is a tree in which one vertex has degree at most <jats:italic>k<\/jats:italic> and all others have degree at most \u2308<jats:italic>k<\/jats:italic>\/2\u2309, then <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>T<\/jats:italic>; <jats:italic>s<\/jats:italic>) = <jats:italic>s<\/jats:italic>(<jats:italic>k<\/jats:italic> \u2212 1) + \u03f5, where \u03f5 = 1 when <jats:italic>k<\/jats:italic> is odd and \u03f5 = 0 when <jats:italic>k<\/jats:italic> is even. For general trees, <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>T<\/jats:italic>; <jats:italic>s<\/jats:italic>) \u2264 2<jats:italic>s<\/jats:italic>(\u0394(<jats:italic>T<\/jats:italic>) \u2212 1).<\/jats:p><jats:p>To study sharpness of the upper bound, consider the <jats:italic>double-star<\/jats:italic><jats:italic>S<jats:sub>a,b<\/jats:sub><\/jats:italic>, the tree whose two non-leaf vertices have degrees <jats:italic>a<\/jats:italic> and <jats:italic>b<\/jats:italic>. If <jats:italic>a<\/jats:italic> \u2264 <jats:italic>b<\/jats:italic>, then <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>S<jats:sub>a,b<\/jats:sub><\/jats:italic>; 2) is 2<jats:italic>b<\/jats:italic> \u2212 2 when <jats:italic>a<\/jats:italic> &lt; <jats:italic>b<\/jats:italic> and <jats:italic>b<\/jats:italic> is even; it is 2<jats:italic>b<\/jats:italic> \u2212 1 otherwise. If <jats:italic>s<\/jats:italic> is fixed and at least 3, then <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>S<jats:sub>b,b<\/jats:sub>;s<\/jats:italic>) = <jats:italic>f<\/jats:italic>(<jats:italic>s<\/jats:italic>)(<jats:italic>b<\/jats:italic> \u2212 1) \u2212 <jats:italic>o<\/jats:italic>(<jats:italic>b<\/jats:italic>), where <jats:italic>f<\/jats:italic>(<jats:italic>s<\/jats:italic>) = 2<jats:italic>s<\/jats:italic> \u2212 3.5 \u2212 <jats:italic>O<\/jats:italic>(<jats:italic>s<\/jats:italic><jats:sup>\u22121<\/jats:sup>).<\/jats:p><jats:p>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 <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>C<\/jats:italic><jats:sub>2<jats:italic>k<\/jats:italic> + 1<\/jats:sub>; <jats:italic>s<\/jats:italic>) \u2265 2<jats:sup><jats:italic>s<\/jats:italic><\/jats:sup> + 1, that <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>C<\/jats:italic><jats:sub>2<jats:italic>k<\/jats:italic><\/jats:sub>; <jats:italic>s<\/jats:italic>) \u2265 2<jats:italic>s<\/jats:italic>, and that <jats:italic>R<\/jats:italic><jats:sub>\u0394<\/jats:sub>(<jats:italic>C<\/jats:italic><jats:sub>4<\/jats:sub>;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.<\/jats:p>","DOI":"10.1017\/s0963548311000617","type":"journal-article","created":{"date-parts":[[2012,3,19]],"date-time":"2012-03-19T15:20:59Z","timestamp":1332170459000},"page":"229-253","source":"Crossref","is-referenced-by-count":8,"title":["Degree Ramsey Numbers of Graphs"],"prefix":"10.1017","volume":"21","author":[{"given":"WILLIAM B.","family":"KINNERSLEY","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KEVIN G.","family":"MILANS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DOUGLAS B.","family":"WEST","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,2,2]]},"reference":[{"key":"S0963548311000617_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72905-8_4"},{"key":"S0963548311000617_ref17","unstructured":"[17] Jiang T. , Milans K. G. and West D. B. Degree Ramsey numbers for cycles and blowups of trees, submitted."},{"key":"S0963548311000617_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010208"},{"key":"S0963548311000617_ref20","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"S0963548311000617_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070115"},{"key":"S0963548311000617_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00006-0"},{"key":"S0963548311000617_ref26","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing","year":"1964","journal-title":"Diskret. Anal."},{"key":"S0963548311000617_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392606"},{"key":"S0963548311000617_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018930"},{"key":"S0963548311000617_ref18","doi-asserted-by":"crossref","unstructured":"[18] Lubotzky A. , Phillips R. and Sarnak P. (1986) Explicit expanders, and the Ramanujan conjectures. In Proc. 18th ACM STOC, pp. 240\u2013246.","DOI":"10.1145\/12130.12154"},{"key":"S0963548311000617_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190090107"},{"key":"S0963548311000617_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261315"},{"key":"S0963548311000617_ref10","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005019"},{"key":"S0963548311000617_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(86)90190-1"},{"key":"S0963548311000617_ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.004"},{"key":"S0963548311000617_ref5","first-page":"17","article-title":"On a bipartite form of the Ramsey problem","volume":"15","author":"Beineke","year":"1975","journal-title":"Congress. Numer."},{"key":"S0963548311000617_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579202"},{"key":"S0963548311000617_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/0118004"},{"key":"S0963548311000617_ref19","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1054"},{"key":"S0963548311000617_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00047-8"},{"key":"S0963548311000617_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90015-0"},{"key":"S0963548311000617_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S030500410002168X"},{"key":"S0963548311000617_ref13","first-page":"251","article-title":"Regul\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl (in German)","volume":"12","author":"Erd\u0151s","year":"1963","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe"},{"key":"S0963548311000617_ref25","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1868"},{"key":"S0963548311000617_ref8","first-page":"167","article-title":"On graphs of Ramsey type","volume":"1","author":"Burr","year":"1976","journal-title":"Ars Combinatoria"},{"key":"S0963548311000617_ref9","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1998.0620"},{"key":"S0963548311000617_ref24","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s004930070024","article-title":"On size Ramsey numbers of graphs with bounded maximum degree","volume":"20","author":"R\u00f6dl","year":"2000","journal-title":"Combinatorica"},{"key":"S0963548311000617_ref23","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000617","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T01:25:09Z","timestamp":1556241909000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000617\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,2]]},"references-count":28,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["S0963548311000617"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000617","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,2]]}}}