{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:29:49Z","timestamp":1777451389327,"version":"3.51.4"},"reference-count":17,"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>R. H. Schelp conjectured that if<jats:italic>G<\/jats:italic>is a graph with |<jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>)| =<jats:italic>R<\/jats:italic>(<jats:italic>P<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>,<jats:italic>P<jats:sub>n<\/jats:sub><\/jats:italic>) such that \u03b4(<jats:italic>G<\/jats:italic>) &gt;<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548311000599_inline1\"><jats:alt-text>$$\\frac{3|V(G)|}{ 4}$<\/jats:alt-text><\/jats:inline-graphic>, then in every 2-colouring of the edges of<jats:italic>G<\/jats:italic>there is a monochromatic<jats:italic>P<jats:sub>n<\/jats:sub><\/jats:italic>. In other words, the Ramsey number of a path does not change if the graph to be coloured is not complete but has large minimum degree.<\/jats:p><jats:p>Here we prove Ramsey-type results that imply the conjecture in a weakened form, first replacing the path by a matching, showing that the star-matching\u2013matching Ramsey number satisfying<jats:italic>R<\/jats:italic>(<jats:italic>S<jats:sub>n<\/jats:sub><\/jats:italic>,<jats:italic>nK<\/jats:italic><jats:sub>2<\/jats:sub>,<jats:italic>nK<\/jats:italic><jats:sub>2<\/jats:sub>) = 3<jats:italic>n<\/jats:italic>\u2212 1. This extends<jats:italic>R<\/jats:italic>(<jats:italic>nK<\/jats:italic><jats:sub>2<\/jats:sub>,<jats:italic>nK<\/jats:italic><jats:sub>2<\/jats:sub>) = 3<jats:italic>n<\/jats:italic>\u2212 1, an old result of Cockayne and Lorimer. Then we extend this further from matchings to connected matchings, and outline how this implies Schelp's conjecture in an asymptotic sense through a standard application of the Regularity Lemma.<\/jats:p><jats:p>It is sad that we are unable to hear Dick Schelp's reaction to our work generated by his conjecture.<\/jats:p>","DOI":"10.1017\/s0963548311000599","type":"journal-article","created":{"date-parts":[[2012,3,19]],"date-time":"2012-03-19T15:20:59Z","timestamp":1332170459000},"page":"179-186","source":"Crossref","is-referenced-by-count":25,"title":["Star Versus Two Stripes Ramsey Numbers and a Conjecture of Schelp"],"prefix":"10.1017","volume":"21","author":[{"given":"ANDR\u00c1S","family":"GY\u00c1RF\u00c1S","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00c1BOR N.","family":"S\u00c1RK\u00d6ZY","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,2,2]]},"reference":[{"key":"S0963548311000599_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.04.049"},{"key":"S0963548311000599_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.07.002"},{"key":"S0963548311000599_ref16","unstructured":"[16] Schelp R. H. A minimum degree condition on a Ramsey graph which arrows a path. Unpublished."},{"key":"S0963548311000599_ref5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","article-title":"On the maximal number of disjoint circuits of a graph","volume":"9","author":"Erd\u0151s","year":"1962","journal-title":"Publ. Math. Debrecen"},{"key":"S0963548311000599_ref8","first-page":"77","volume-title":"Ramsey Theory: Yesterday, Today and Tomorrow","author":"Gy\u00e1rf\u00e1s","year":"2010"},{"key":"S0963548311000599_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700029554"},{"key":"S0963548311000599_ref4","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1975-005-0"},{"key":"S0963548311000599_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0043-4"},{"key":"S0963548311000599_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.09.001"},{"key":"S0963548311000599_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.12.002"},{"key":"S0963548311000599_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20231"},{"key":"S0963548311000599_ref1","unstructured":"[1] Benevides F. S. , \u0141uczak T. , Scott A. , Skokan J. and White M. (2012) Monochromatic cycles in 2-coloured graphs. Combin. Probab. Comput. 21 57\u201387."},{"key":"S0963548311000599_ref17","unstructured":"[17] Szemer\u00e9di E. (1978) Regular partitions of graphs. In Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes: Orsay 1976, Vol. 260 of Colloques Internationaux CNRS, pp. 399\u2013401."},{"key":"S0963548311000599_ref7","first-page":"167","article-title":"On Ramsey type problems","volume":"10","author":"Gerencs\u00e9r","year":"1967","journal-title":"Ann. Univ. Sci. E\u00f6tv\u00f6s, Budapest"},{"key":"S0963548311000599_ref13","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1998.1874"},{"key":"S0963548311000599_ref15","unstructured":"[15] Schelp R. H. Some Ramsey\u2013Tur\u00e1n type problems and related questions. Manuscript, to appear in a special volume of Discrete Math."},{"key":"S0963548311000599_ref12","unstructured":"[12] Koml\u00f3s J. and Simonovits M. (1996) Szemer\u00e9di's Regularity Lemma and its applications in Graph Theory. In Combinatorics: Paul Erd\u0151s is Eighty ( Mikl\u00f3s D. , S\u00f3s V. T. and Sz\u0151nyi T. , eds), Vol. 2 of Bolyai Society Mathematical Studies, pp. 295\u2013352."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548311000599","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,21]],"date-time":"2023-06-21T08:16:22Z","timestamp":1687335382000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548311000599\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,2]]},"references-count":17,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["S0963548311000599"],"URL":"https:\/\/doi.org\/10.1017\/s0963548311000599","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]]}}}