---
OA_place: publisher
OA_type: hybrid
_id: '18753'
abstract:
- lang: eng
text: "We continue a line of research which studies which hereditary families of
digraphs have bounded dichromatic number. For a class of digraphs C, a hero in
\ C is any digraph H\r\n such that H -free digraphs in C have bounded dichromatic
number. We show that if F\r\n is an oriented star of degree at least five, the
only heroes for the class of F -free digraphs are transitive tournaments. For
oriented stars F of degree exactly four, we show the only heroes in F -free
digraphs are transitive tournaments, or possibly special joins of transitive tournaments.
Aboulker et al. characterized the set of heroes of {H,K1+P2→} -free digraphs
almost completely, and we show the same characterization for the class of {H,rK1+P3→}
-free digraphs. Lastly, we show that if we forbid two \"valid\" orientations of
brooms, then every transitive tournament is a hero for this class of digraphs."
acknowledgement: "We thank the anonymous referees for their careful proofreading which
helped improve the presentation of this paper. We also thank one of the anonymous
referees for pointing out our construction implies Theorem 1.7!\r\nBenjamin Moore
finished this project while a postdoctoral researcher at Charles University, and
was supported by project 22-17398S (Flows and cycles in graphs on surfaces) of the
Czech Science Foundation. Benjamin Moore is currently funded by RANDSTRUCT No. 101076777,
and appreciates the gracious support. We acknowledge the support of the Natural
Sciences and Engineering Research Council of Canada (NSERC), [funding reference
number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches
en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912].
This project was funded in part by the Government of Ontario ."
article_number: '104104'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Alvaro
full_name: Carbonero, Alvaro
last_name: Carbonero
- first_name: Hidde
full_name: Koerts, Hidde
last_name: Koerts
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Sophie
full_name: Spirkl, Sophie
last_name: Spirkl
citation:
ama: Carbonero A, Koerts H, Moore B, Spirkl S. On heroes in digraphs with forbidden
induced forests. European Journal of Combinatorics. 2025;125. doi:10.1016/j.ejc.2024.104104
apa: Carbonero, A., Koerts, H., Moore, B., & Spirkl, S. (2025). On heroes in
digraphs with forbidden induced forests. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2024.104104
chicago: Carbonero, Alvaro, Hidde Koerts, Benjamin Moore, and Sophie Spirkl. “On
Heroes in Digraphs with Forbidden Induced Forests.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2024.104104.
ieee: A. Carbonero, H. Koerts, B. Moore, and S. Spirkl, “On heroes in digraphs with
forbidden induced forests,” European Journal of Combinatorics, vol. 125.
Elsevier, 2025.
ista: Carbonero A, Koerts H, Moore B, Spirkl S. 2025. On heroes in digraphs with
forbidden induced forests. European Journal of Combinatorics. 125, 104104.
mla: Carbonero, Alvaro, et al. “On Heroes in Digraphs with Forbidden Induced Forests.”
European Journal of Combinatorics, vol. 125, 104104, Elsevier, 2025, doi:10.1016/j.ejc.2024.104104.
short: A. Carbonero, H. Koerts, B. Moore, S. Spirkl, European Journal of Combinatorics
125 (2025).
corr_author: '1'
date_created: 2025-01-05T23:01:55Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-05-19T14:06:00Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2024.104104
external_id:
arxiv:
- '2306.04710'
isi:
- '001400113700001'
file:
- access_level: open_access
checksum: 2c75f78f40ebb93d16fe3765bda2905a
content_type: application/pdf
creator: dernst
date_created: 2025-04-16T09:16:25Z
date_updated: 2025-04-16T09:16:25Z
file_id: '19577'
file_name: 2025_EuropJournCombinatorics_Carbonero.pdf
file_size: 1110657
relation: main_file
success: 1
file_date_updated: 2025-04-16T09:16:25Z
fulldoi: https://doi.org/10.1016/j.ejc.2024.104104
has_accepted_license: '1'
intvolume: ' 125'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On heroes in digraphs with forbidden induced forests
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 125
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19002'
abstract:
- lang: eng
text: "A k-subcolouring of a graph G is a function f : V (G) → {0,...,k − 1} such
that the set of\r\nvertices coloured i induce a disjoint union of cliques. The
subchromatic number, χsub(G),\r\nis the minimum k such that G admits a k-subcolouring.
Nešetril, ˇ Ossona de Mendez,\r\nPilipczuk, and Zhu (2020), recently raised the
problem of finding tight upper bounds for\r\nχsub(G2) when G is planar. We show
that χsub(G2) ≤ 43 when G is planar, improving\r\ntheir bound of 135. We give
even better bounds when the planar graph G has larger girth.\r\nMoreover, we show
that χsub(G3) ≤ 95, improving the previous bound of 364. For these\r\nwe adapt
some recent techniques of Almulhim and Kierstead (2022), while also extending\r\nthe
decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez,\r\nQuiroz,
Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that
these\r\ndecompositions are the precursors of the graph product structure theorem
of planar graphs.\r\nWe give improved bounds for χsub(Gp) for all p ≥ 2, whenever
G has bounded treewidth,\r\nbounded simple treewidth, bounded genus, or excludes
a clique or biclique as a minor.\r\nFor this we introduce a family of parameters
which form a gradation between the strong\r\nand the weak colouring numbers. We
give upper bounds for these parameters for graphs\r\ncoming from such classes.\r\nFinally,
we give a 2-approximation algorithm for the subchromatic number of graphs\r\nhaving
a layering in which each layer has bounded cliquewidth and this layering is\r\ncomputable
in polynomial time (like the class of all dth powers of planar graphs, for fixed\r\nd).
This algorithm works even if the power p and the graph G is unknown."
acknowledgement: We thank an anonymous referee for pointing out an error in an earlier
version of Theorem 3.1. We also thank an anonymous referee for pointing out numerous
typos in an earlier version of the paper.
article_number: '114377'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Pedro P.
full_name: Cortés, Pedro P.
last_name: Cortés
- first_name: Pankaj
full_name: Kumar, Pankaj
last_name: Kumar
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Patrice
full_name: Ossona de Mendez, Patrice
last_name: Ossona de Mendez
- first_name: Daniel A.
full_name: Quiroz, Daniel A.
last_name: Quiroz
citation:
ama: Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. Subchromatic numbers
of powers of graphs with excluded minors. Discrete Mathematics. 2025;348(4).
doi:10.1016/j.disc.2024.114377
apa: Cortés, P. P., Kumar, P., Moore, B., Ossona de Mendez, P., & Quiroz, D.
A. (2025). Subchromatic numbers of powers of graphs with excluded minors. Discrete
Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.114377
chicago: Cortés, Pedro P., Pankaj Kumar, Benjamin Moore, Patrice Ossona de Mendez,
and Daniel A. Quiroz. “Subchromatic Numbers of Powers of Graphs with Excluded
Minors.” Discrete Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.disc.2024.114377.
ieee: P. P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, and D. A. Quiroz, “Subchromatic
numbers of powers of graphs with excluded minors,” Discrete Mathematics,
vol. 348, no. 4. Elsevier, 2025.
ista: Cortés PP, Kumar P, Moore B, Ossona de Mendez P, Quiroz DA. 2025. Subchromatic
numbers of powers of graphs with excluded minors. Discrete Mathematics. 348(4),
114377.
mla: Cortés, Pedro P., et al. “Subchromatic Numbers of Powers of Graphs with Excluded
Minors.” Discrete Mathematics, vol. 348, no. 4, 114377, Elsevier, 2025,
doi:10.1016/j.disc.2024.114377.
short: P.P. Cortés, P. Kumar, B. Moore, P. Ossona de Mendez, D.A. Quiroz, Discrete
Mathematics 348 (2025).
corr_author: '1'
date_created: 2025-02-05T06:51:08Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-09-30T10:25:15Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.disc.2024.114377
external_id:
arxiv:
- '2306.02195'
isi:
- '001401656900001'
file:
- access_level: open_access
checksum: 6723cbb02b6aea0d05f37d167da00c03
content_type: application/pdf
creator: dernst
date_created: 2025-05-05T12:56:12Z
date_updated: 2025-05-05T12:56:12Z
file_id: '19657'
file_name: 2025_DiscreteMath_Cortes.pdf
file_size: 850988
relation: main_file
success: 1
file_date_updated: 2025-05-05T12:56:12Z
fulldoi: https://doi.org/10.1016/j.disc.2024.114377
has_accepted_license: '1'
intvolume: ' 348'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Subchromatic numbers of powers of graphs with excluded minors
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: 348
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19879'
abstract:
- lang: eng
text: We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations,
i.e., plane graphs where all faces except possibly for the outer one have length
three, all vertices not incident with the outer face have even degree, and exactly
the vertices incident with the outer face are precolored. We give a necessary
topological condition for the precoloring to extend, and give a complete characterization
when the outer face has length at most five and when all vertices of the outer
face have odd degree and are colored using only three colors.
acknowledgement: Supported by project 22-17398S (Flows and cycles in graphs on surfaces)
of Czech Science Foundation. An extended abstract appeared in Proceedings of the
12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’23)
article_number: '104138'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Zdeněk
full_name: Dvořák, Zdeněk
last_name: Dvořák
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Michaela
full_name: Seifrtová, Michaela
last_name: Seifrtová
- first_name: Robert
full_name: Šámal, Robert
last_name: Šámal
citation:
ama: Dvořák Z, Moore B, Seifrtová M, Šámal R. Precoloring extension in planar near-Eulerian-triangulations.
European Journal of Combinatorics. 2025;127. doi:10.1016/j.ejc.2025.104138
apa: Dvořák, Z., Moore, B., Seifrtová, M., & Šámal, R. (2025). Precoloring extension
in planar near-Eulerian-triangulations. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2025.104138
chicago: Dvořák, Zdeněk, Benjamin Moore, Michaela Seifrtová, and Robert Šámal. “Precoloring
Extension in Planar Near-Eulerian-Triangulations.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104138.
ieee: Z. Dvořák, B. Moore, M. Seifrtová, and R. Šámal, “Precoloring extension in
planar near-Eulerian-triangulations,” European Journal of Combinatorics,
vol. 127. Elsevier, 2025.
ista: Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar
near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138.
mla: Dvořák, Zdeněk, et al. “Precoloring Extension in Planar Near-Eulerian-Triangulations.”
European Journal of Combinatorics, vol. 127, 104138, Elsevier, 2025, doi:10.1016/j.ejc.2025.104138.
short: Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics
127 (2025).
corr_author: '1'
date_created: 2025-06-23T13:54:46Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2025-09-30T13:42:59Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104138
external_id:
arxiv:
- '2312.13061'
isi:
- '001443061400001'
file:
- access_level: open_access
checksum: 8b3585df45b25091fba9bee9854b7d01
content_type: application/pdf
creator: dernst
date_created: 2025-06-24T06:33:30Z
date_updated: 2025-06-24T06:33:30Z
file_id: '19887'
file_name: 2025_EuropJournCombinatorics_Dvorak.pdf
file_size: 564203
relation: main_file
success: 1
file_date_updated: 2025-06-24T06:33:30Z
fulldoi: https://doi.org/10.1016/j.ejc.2025.104138
has_accepted_license: '1'
intvolume: ' 127'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Precoloring extension in planar near-Eulerian-triangulations
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: 127
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20007'
abstract:
- lang: eng
text: 'There is no known polynomial-time algorithm for graph isomorphism testing,
but elementary combinatorial “refinement” algorithms seem to be very efficient
in practice. Some philosophical justification for this phenomenon is provided
by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time
combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex
classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”)
yields a so-called canonical labelling scheme for “almost all graphs”. More precisely,
for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm
assigns labels to vertices in a way that easily permits isomorphism-testing against
any other graph.'
acknowledgement: All authors were supported by ERC Starting Grant “RANDSTRUCT” No.
101076777. Michael Anastos was also supported in part by the Austrian Science Fund
(FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.
For Open Access purposes, the authors have applied a CC BY public copyright license
to any author accepted manuscript version arising from this submission.
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
citation:
ama: 'Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In:
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association
for Computing Machinery; 2025:2098-2106. doi:10.1145/3717823.3718173'
apa: 'Anastos, M., Kwan, M. A., & Moore, B. (2025). Smoothed analysis for graph
isomorphism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing
(pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. https://doi.org/10.1145/3717823.3718173'
chicago: Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis
for Graph Isomorphism.” In Proceedings of the 57th Annual ACM Symposium on
Theory of Computing, 2098–2106. Association for Computing Machinery, 2025.
https://doi.org/10.1145/3717823.3718173.
ieee: M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,”
in Proceedings of the 57th Annual ACM Symposium on Theory of Computing,
Prague, Czechia, 2025, pp. 2098–2106.
ista: 'Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism.
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium
on Theory of Computing, 2098–2106.'
mla: Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 2098–106, doi:10.1145/3717823.3718173.
short: M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM
Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp.
2098–2106.
conference:
end_date: 2025-06-27
location: Prague, Czechia
name: 'STOC: Symposium on Theory of Computing'
start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2025-07-14T06:33:50Z
day: '15'
ddc:
- '000'
department:
- _id: MaKw
doi: 10.1145/3717823.3718173
ec_funded: 1
external_id:
arxiv:
- '2410.06095'
file:
- access_level: open_access
checksum: cf0ab9cb9c6abda188de13dc3f9a4c9b
content_type: application/pdf
creator: dernst
date_created: 2025-07-14T06:13:10Z
date_updated: 2025-07-14T06:13:10Z
file_id: '20012'
file_name: 2025_STOC_Anastos.pdf
file_size: 706445
relation: main_file
success: 1
file_date_updated: 2025-07-14T06:13:10Z
fulldoi: https://doi.org/10.1145/3717823.3718173
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2098-2106
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400715105'
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Smoothed analysis for graph isomorphism
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20320'
abstract:
- lang: eng
text: "The pseudoforest version of the Strong Nine Dragon Tree Conjecture states
that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most
2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in
one pseudoforest F the components of F have at most d edges. This was proven in
2020 in Grout and Moore (2020). We strengthen this\r\ntheorem by showing that
we can find such a decomposition where additionally F is acyclic, the diameter
of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ +
1 if\r\nd ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N,
we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter
bounds are best possible as an\r\nextension for both the Strong Nine Dragon Tree
Conjecture for pseudoforests and its original conjecture for forests. In fact,
they are still optimal even if we only enforce F to have any constant maximum
degree, instead of enforcing every component of F to have at most d edges."
acknowledgement: This work was completed while Benjamin Moore was a postdoc at Charles
University, supported by project 22-17398S (Flows and cycles in graphs on surfaces)
of Czech Science Foundation, Czechia.
article_number: '104214'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Sebastian
full_name: Mies, Sebastian
last_name: Mies
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Evelyne
full_name: Smith-Roberge, Evelyne
last_name: Smith-Roberge
citation:
ama: Mies S, Moore B, Smith-Roberge E. Beyond the pseudoforest strong Nine Dragon
Tree theorem. European Journal of Combinatorics. 2025;130(12). doi:10.1016/j.ejc.2025.104214
apa: Mies, S., Moore, B., & Smith-Roberge, E. (2025). Beyond the pseudoforest
strong Nine Dragon Tree theorem. European Journal of Combinatorics. Elsevier.
https://doi.org/10.1016/j.ejc.2025.104214
chicago: Mies, Sebastian, Benjamin Moore, and Evelyne Smith-Roberge. “Beyond the
Pseudoforest Strong Nine Dragon Tree Theorem.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104214.
ieee: S. Mies, B. Moore, and E. Smith-Roberge, “Beyond the pseudoforest strong Nine
Dragon Tree theorem,” European Journal of Combinatorics, vol. 130, no.
12. Elsevier, 2025.
ista: Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine
Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.
mla: Mies, Sebastian, et al. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.”
European Journal of Combinatorics, vol. 130, no. 12, 104214, Elsevier,
2025, doi:10.1016/j.ejc.2025.104214.
short: S. Mies, B. Moore, E. Smith-Roberge, European Journal of Combinatorics 130
(2025).
corr_author: '1'
date_created: 2025-09-10T05:36:50Z
date_published: 2025-12-01T00:00:00Z
date_updated: 2025-12-30T10:19:10Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104214
external_id:
arxiv:
- '2310.00931'
isi:
- '001529769300002'
file:
- access_level: open_access
checksum: b1536e9256c4510a0e21452032e43a26
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T10:18:56Z
date_updated: 2025-12-30T10:18:56Z
file_id: '20913'
file_name: 2025_EuropJournCombinatorics_Mies.pdf
file_size: 737845
relation: main_file
success: 1
file_date_updated: 2025-12-30T10:18:56Z
fulldoi: https://doi.org/10.1016/j.ejc.2025.104214
has_accepted_license: '1'
intvolume: ' 130'
isi: 1
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Beyond the pseudoforest strong Nine Dragon Tree theorem
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 130
year: '2025'
...
---
_id: '15163'
abstract:
- lang: eng
text: For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components
has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of
a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ
where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding
whether a given graph has such a decomposition is NP-complete if both k and ℓ
are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before
this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness
result answers a question of Bermond et al. from 1984. We also show that planar
graphs of girth at least nine decompose into a linear forest and a matching, which
in particular is stronger than 3-edge-colouring such graphs.
acknowledgement: We wish to thank Dániel Marx and András Sebő for making us aware
of the results in [8] and some clarifications on them.
article_number: '113962'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Rutger
full_name: Campbell, Rutger
last_name: Campbell
- first_name: Florian
full_name: Hörsch, Florian
last_name: Hörsch
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
citation:
ama: Campbell R, Hörsch F, Moore B. Decompositions into two linear forests of bounded
lengths. Discrete Mathematics. 2024;347(6). doi:10.1016/j.disc.2024.113962
apa: Campbell, R., Hörsch, F., & Moore, B. (2024). Decompositions into two linear
forests of bounded lengths. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.113962
chicago: Campbell, Rutger, Florian Hörsch, and Benjamin Moore. “Decompositions into
Two Linear Forests of Bounded Lengths.” Discrete Mathematics. Elsevier,
2024. https://doi.org/10.1016/j.disc.2024.113962.
ieee: R. Campbell, F. Hörsch, and B. Moore, “Decompositions into two linear forests
of bounded lengths,” Discrete Mathematics, vol. 347, no. 6. Elsevier, 2024.
ista: Campbell R, Hörsch F, Moore B. 2024. Decompositions into two linear forests
of bounded lengths. Discrete Mathematics. 347(6), 113962.
mla: Campbell, Rutger, et al. “Decompositions into Two Linear Forests of Bounded
Lengths.” Discrete Mathematics, vol. 347, no. 6, 113962, Elsevier, 2024,
doi:10.1016/j.disc.2024.113962.
short: R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024).
corr_author: '1'
date_created: 2024-03-24T23:00:58Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2025-09-04T13:10:26Z
day: '01'
department:
- _id: MaKw
doi: 10.1016/j.disc.2024.113962
external_id:
arxiv:
- '2301.11615'
isi:
- '001226893800001'
fulldoi: https://doi.org/10.1016/j.disc.2024.113962
intvolume: ' 347'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.11615
month: '06'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decompositions into two linear forests of bounded lengths
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 347
year: '2024'
...