{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:59:49Z","timestamp":1775717989403,"version":"3.50.1"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T00:00:00Z","timestamp":1774396800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T00:00:00Z","timestamp":1774396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"HUN-REN Alfr\u00e9d R\u00e9nyi Institute of Mathematics"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A subset\n                    <jats:italic>X<\/jats:italic>\n                    of vertices in a graph\n                    <jats:italic>G<\/jats:italic>\n                    is a\n                    <jats:italic>diameter 2 subset<\/jats:italic>\n                    if the distance of any two vertices of\n                    <jats:italic>X<\/jats:italic>\n                    is at most two\n                    <jats:italic>in G[X]<\/jats:italic>\n                    . Relaxing this notion, a subset\n                    <jats:italic>X<\/jats:italic>\n                    of vertices in a graph\n                    <jats:italic>G<\/jats:italic>\n                    is a\n                    <jats:italic>2-reachable subset<\/jats:italic>\n                    if the distance of any two vertices of\n                    <jats:italic>X<\/jats:italic>\n                    is at most two\n                    <jats:italic>in G<\/jats:italic>\n                    . Related to recent attempts to strengthen a well-known conjecture of Ryser, English et al. conjectured that the vertices of a 2-edge-colored cocktail party graph (the graph obtained from a complete graph with an even number of vertices by deleting a perfect matching) can be covered by the vertices of two monochromatic diameter 2 subsets. In this note we prove the relaxed form of this conjecture, replacing diameter 2 by 2-reachable. An immediate corollary is that 2-colored cocktail party graphs on\n                    <jats:italic>n<\/jats:italic>\n                    vertices must contain a monochromatic 2-reachable subset with at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n\\over 2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mfrac>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mfrac>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    vertices (and this is best possible).\n                  <\/jats:p>","DOI":"10.1007\/s00373-026-03036-6","type":"journal-article","created":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T08:19:49Z","timestamp":1774426789000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["2-Reachable Subsets in Two-Colored Graphs"],"prefix":"10.1007","volume":"42","author":[{"given":"Andr\u00e1s","family":"Gy\u00e1rf\u00e1s","sequence":"first","affiliation":[]},{"given":"G\u00e1bor N.","family":"S\u00e1rk\u00f6zy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,3,25]]},"reference":[{"issue":"1","key":"3036_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s004930170001","volume":"21","author":"R Aharoni","year":"2001","unstructured":"Aharoni, R.: Ryser\u2019s conjecture for tripartite 3-graphs. Combinatorica 21(1), 1\u20134 (2001)","journal-title":"Combinatorica"},{"key":"3036_CR2","doi-asserted-by":"crossref","unstructured":"L. DeBiasio, A. Girao, P. Haxell, M. Stein, A bounded diameter strengthening of K\u00f6nig\u2019s theorem, to appear in SIAM Journal on Discrete Mathematics 39(2), 1269\u20131273 (2025) arXiv:2409.18250","DOI":"10.1137\/24M1701022"},{"key":"3036_CR3","doi-asserted-by":"publisher","first-page":"P4.37","DOI":"10.37236\/9914","volume":"28","author":"L DeBiasio","year":"2021","unstructured":"DeBiasio, L., Kamel, Y., McCourt, G., Sheats, H.: Generalizations and strengthenings of Ryser\u2019s conjecture. Electron. J. Combin. 28, P4.37 (2021)","journal-title":"Electron. J. Combin."},{"key":"3036_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/PL00021189","volume":"15","author":"P Erd\u0151s","year":"1999","unstructured":"Erd\u0151s, P., Fowler, T.: Finding large $$p$$-colored diameter two subgraphs. Graphs and Combinatorics 15, 21\u201327 (1999)","journal-title":"Graphs and Combinatorics"},{"issue":"2","key":"3036_CR5","doi-asserted-by":"publisher","first-page":"139","DOI":"10.4310\/JOC.2024.v15.n2.a1","volume":"15","author":"S English","year":"2024","unstructured":"English, S., McCourt, G., Mattes, C., Phillips, M.: Low diameter monochromatic covers of complete bipartite graphs. J. Combinatorics 15(2), 139\u2013157 (2024)","journal-title":"J. Combinatorics"},{"key":"3036_CR6","unstructured":"Henderson, J.R.: Permutation decomposition of $$(0-1)$$-matrices and decomposition transversals, Ph.D. Thesis, California Institute of Technology, 1971, https:\/\/core.ac.uk\/download\/pdf\/11814656.pdf"},{"key":"3036_CR7","unstructured":"Gy\u00e1rf\u00e1s, A.: Partition coverings and blocking sets in hypergraphs, Communications of the Computer and Automation Institute of the Hungarian Academy of Sciences71 (1977), in Hungarian"},{"key":"3036_CR8","doi-asserted-by":"publisher","first-page":"R8","DOI":"10.37236\/1293","volume":"4","author":"A Gy\u00e1rf\u00e1s","year":"1997","unstructured":"Gy\u00e1rf\u00e1s, A.: Fruit salad. Electron. J. Combin. 4, R8 (1997)","journal-title":"Electron. J. Combin."},{"key":"3036_CR9","unstructured":"Gy\u00e1rf\u00e1s, A., S\u00e1rk\u00f6zy, G.N.: Bounded diameter variations of Ryser\u2019s conjecture, arXiv:2505.02564"},{"key":"3036_CR10","first-page":"116","volume":"38","author":"D K\u00f6nig","year":"1931","unstructured":"K\u00f6nig, D.: Graphs and matrices. Matematikai \u00e9s Fizikai Lapok 38, 116\u2013119 (1931)","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"3036_CR11","doi-asserted-by":"publisher","first-page":"225","DOI":"10.4064\/fm231-3-2","volume":"231","author":"L Mili\u010devi\u010d","year":"2015","unstructured":"Mili\u010devi\u010d, L.: Commuting contractive families. Fundam. Math. 231, 225\u2013272 (2015)","journal-title":"Fundam. Math."},{"key":"3036_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.2298\/AADM170204022M","volume":"13","author":"L Mili\u010devi\u010d","year":"2019","unstructured":"Mili\u010devi\u010d, L.: Covering complete graphs by monochromatically bounded sets. Applicable Analysis and Discrete Mathematics 13, 85\u2013110 (2019)","journal-title":"Applicable Analysis and Discrete Mathematics"},{"key":"3036_CR13","unstructured":"Tuza, Zs.: Some special cases of Ryser\u2019s Conjecture, unpublished manuscript, 1979"},{"key":"3036_CR14","first-page":"201","volume":"16","author":"Ryser\u2019s conjecture on transversals of r-partite hypergraphs","year":"1983","unstructured":"Ryser\u2019s conjecture on transversals of r-partite hypergraphs: Tuza, Zs. Ars Combin. 16, 201\u2013209 (1983)","journal-title":"Ars Combin."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-026-03036-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-026-03036-6","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-026-03036-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:15:47Z","timestamp":1775715347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-026-03036-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,25]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["3036"],"URL":"https:\/\/doi.org\/10.1007\/s00373-026-03036-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,25]]},"assertion":[{"value":"8 July 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"43"}}