---
OA_place: publisher
OA_type: hybrid
_id: '19503'
abstract:
- lang: eng
  text: "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  s,t≥1
    there exists a finite number  F(s,t)\r\nsuch that the vertex set of every digraph
    of minimum out-degree at least  F(s,t) can be partitioned into non-empty parts
    \ A  and  B  such that the subdigraphs induced on  A\r\n  and  B  have minimum
    out-degree at least  s  and  t , respectively.\r\nIn this short note, we prove
    that if  F(2,2)  exists, then all the numbers  F(s,t)  with  s,t≥1\r\n  exist
    and satisfy  F(s,t)=Θ(s+t) . In consequence, the problem of Alon and Stiebitz
    reduces to the case  s=t=2 . Moreover, the numbers  F(s,t)  with  s,t≥2  either
    all exist and grow linearly, or all of them do not exist."
acknowledgement: Funded by SNSF Ambizione grant No. 216071. This project has received
  funding from the European Union’s Horizon 2020 research and innovation programme
  under the Marie Skłodowska-Curie grant agreement No, 101034413. Funded by SNSF grant
  CRSII5, 173721.
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Micha
  full_name: Christoph, Micha
  last_name: Christoph
- first_name: Kalina H
  full_name: Petrova, Kalina H
  id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
  last_name: Petrova
- first_name: Raphael
  full_name: Steiner, Raphael
  last_name: Steiner
citation:
  ama: Christoph M, Petrova KH, Steiner R. A note on digraph splitting. <i>Combinatorics
    Probability and Computing</i>. 2025;34(4):559-564. doi:<a href="https://doi.org/10.1017/S0963548325000045">10.1017/S0963548325000045</a>
  apa: Christoph, M., Petrova, K. H., &#38; Steiner, R. (2025). A note on digraph
    splitting. <i>Combinatorics Probability and Computing</i>. Cambridge University
    Press. <a href="https://doi.org/10.1017/S0963548325000045">https://doi.org/10.1017/S0963548325000045</a>
  chicago: Christoph, Micha, Kalina H Petrova, and Raphael Steiner. “A Note on Digraph
    Splitting.” <i>Combinatorics Probability and Computing</i>. Cambridge University
    Press, 2025. <a href="https://doi.org/10.1017/S0963548325000045">https://doi.org/10.1017/S0963548325000045</a>.
  ieee: M. Christoph, K. H. Petrova, and R. Steiner, “A note on digraph splitting,”
    <i>Combinatorics Probability and Computing</i>, vol. 34, no. 4. Cambridge University
    Press, pp. 559–564, 2025.
  ista: Christoph M, Petrova KH, Steiner R. 2025. A note on digraph splitting. Combinatorics
    Probability and Computing. 34(4), 559–564.
  mla: Christoph, Micha, et al. “A Note on Digraph Splitting.” <i>Combinatorics Probability
    and Computing</i>, vol. 34, no. 4, Cambridge University Press, 2025, pp. 559–64,
    doi:<a href="https://doi.org/10.1017/S0963548325000045">10.1017/S0963548325000045</a>.
  short: M. Christoph, K.H. Petrova, R. Steiner, Combinatorics Probability and Computing
    34 (2025) 559–564.
date_created: 2025-04-06T22:01:32Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2025-09-30T11:26:00Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1017/S0963548325000045
ec_funded: 1
external_id:
  arxiv:
  - '2310.08449'
  isi:
  - '001449245700001'
file:
- access_level: open_access
  checksum: 98491e59b4f0d05d69f608bbd5706f1a
  content_type: application/pdf
  creator: dernst
  date_created: 2025-08-05T12:54:06Z
  date_updated: 2025-08-05T12:54:06Z
  file_id: '20135'
  file_name: 2025_CombProbComputing_Christoph.pdf
  file_size: 188818
  relation: main_file
  success: 1
file_date_updated: 2025-08-05T12:54:06Z
has_accepted_license: '1'
intvolume: '        34'
isi: 1
issue: '4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
page: 559-564
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Combinatorics Probability and Computing
publication_identifier:
  eissn:
  - 1469-2163
  issn:
  - 0963-5483
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: A note on digraph splitting
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 34
year: '2025'
...