{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T05:46:46Z","timestamp":1775800006012,"version":"3.50.1"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T00:00:00Z","timestamp":1742515200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    A tantalizing open problem, posed independently by Stiebitz in 1995 and by Alon in 1996 and again in 2006, asks whether for every pair of integers\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline1.png\"\/>\n                        <jats:tex-math>$s,t \\ge 1$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    there exists a finite number\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline2.png\"\/>\n                        <jats:tex-math>$F(s,t)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    such that the vertex set of every digraph of minimum out-degree at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline3.png\"\/>\n                        <jats:tex-math>$F(s,t)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    can be partitioned into non-empty parts\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline4.png\"\/>\n                        <jats:tex-math>$A$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline5.png\"\/>\n                        <jats:tex-math>$B$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    such that the subdigraphs induced on\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline6.png\"\/>\n                        <jats:tex-math>$A$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline7.png\"\/>\n                        <jats:tex-math>$B$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    have minimum out-degree at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline8.png\"\/>\n                        <jats:tex-math>$s$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline9.png\"\/>\n                        <jats:tex-math>$t$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , respectively.\n                  <\/jats:p>\n                  <jats:p>\n                    In this short note, we prove that if\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline10.png\"\/>\n                        <jats:tex-math>$F(2,2)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    exists, then all the numbers\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline11.png\"\/>\n                        <jats:tex-math>$F(s,t)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline12.png\"\/>\n                        <jats:tex-math>$s,t\\ge 1$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    exist and satisfy\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline13.png\"\/>\n                        <jats:tex-math>$F(s,t)=\\Theta (s+t)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . In consequence, the problem of Alon and Stiebitz reduces to the case\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline14.png\"\/>\n                        <jats:tex-math>$s=t=2$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Moreover, the numbers\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline15.png\"\/>\n                        <jats:tex-math>$F(s,t)$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0963548325000045_inline16.png\"\/>\n                        <jats:tex-math>$s,t \\ge 2$<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    either all exist and grow linearly, or all of them do not exist.\n                  <\/jats:p>","DOI":"10.1017\/s0963548325000045","type":"journal-article","created":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T06:36:30Z","timestamp":1742538990000},"page":"559-564","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["A note on digraph splitting"],"prefix":"10.1017","volume":"34","author":[{"given":"Micha","family":"Christoph","sequence":"first","affiliation":[{"name":"Institute of Theoretical Computer Science, ETH Z\u00fcrich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kalina","family":"Petrova","sequence":"additional","affiliation":[{"name":"Institute of Science and Technology Austria (ISTA)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4234-6136","authenticated-orcid":false,"given":"Raphael","family":"Steiner","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Computer Science, ETH Z\u00fcrich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,3,21]]},"reference":[{"key":"S0963548325000045_ref10","doi-asserted-by":"publisher","DOI":"10.37236\/6762"},{"key":"S0963548325000045_ref5","doi-asserted-by":"publisher","DOI":"10.37236\/10067"},{"key":"S0963548325000045_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80025-1"},{"key":"S0963548325000045_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.23016"},{"key":"S0963548325000045_ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2018.03.005"},{"key":"S0963548325000045_ref17","first-page":"56","volume-title":"Decomposition of Graphs and Digraphs","volume":"309","author":"Stiebitz","year":"1995"},{"key":"S0963548325000045_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2018.04.027"},{"key":"S0963548325000045_ref11","doi-asserted-by":"publisher","DOI":"10.37236\/6410"},{"key":"S0963548325000045_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199611)23:3<321::AID-JGT12>3.0.CO;2-H"},{"key":"S0963548325000045_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831700044X"},{"key":"S0963548325000045_ref14","unstructured":"[14] Open Problem Garden (2013) Splitting digraphs with minimum outdegree constraints. Available at: http:\/\/www.openproblemgarden.org\/op\/splitting_a_digraph_with_minimum_outdegree_constraints."},{"key":"S0963548325000045_ref12","volume-title":"PhD thesis","author":"Lochet","year":"2018"},{"key":"S0963548325000045_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22476"},{"key":"S0963548325000045_ref3","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548306008042"},{"key":"S0963548325000045_ref6","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.70010"},{"key":"S0963548325000045_ref7","doi-asserted-by":"publisher","DOI":"10.37236\/6923"},{"key":"S0963548325000045_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90172-9"},{"key":"S0963548325000045_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070204"},{"key":"S0963548325000045_ref2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0062"},{"key":"S0963548325000045_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579195"},{"key":"S0963548325000045_ref13","first-page":"237","article-title":"On decompositions of graphs","volume":"1","author":"Lov\u00e1sz","year":"1966","journal-title":"Stud. Sci. Math. Hung."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000045","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:48:53Z","timestamp":1775796533000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000045\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,21]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["S0963548325000045"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000045","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,21]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (https:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}