---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '20482'
abstract:
- lang: eng
text: 'In his study of graph codes, Alon introduced the concept of the odd-Ramsey
number of a family of graphs H in Kn, defined as the minimum number of colours
needed to colour the edges of K so that every copy of a graph H E H intersects
some colour class in an odd number of edges. In this paper, we focus on complete
bipartite graphs. First, we completely resolve the problem when H is the family
of all spanning complete bipartite graphs on n vertices. We then focus on its
subfamilies, that is, {Kt,n-t : t E T} for a fixed set of integers T c [[n/2]].
We prove that the odd-Ramsey problem is equivalent to determining the maximum
dimension of a linear binary code avoiding codewords of given weights, and leverage
known results from coding theory to deduce asymptotically tight bounds in our
setting. We conclude with bounds for the odd-Ramsey numbers of fixed (that is,
non-spanning) complete bipartite subgraphs.'
acknowledgement: "The authors would like to thank Gilles Zémor for a helpful clarification
on [3], Deepak Bal and Patrick Bennett for bringing [25] to their attention, and
both referees for several helpful comments.\r\nS.B.: Most of this research was conducted
while the author was at the School of Mathematics, University of Birmingham, Birmingham,
United Kingdom. The research leading to these results was supported by EPSRC, United
Kingdom, grant no. EP/V048287/1 and by ERC Advanced Grants “GeoScape”, no. 882971
and “ERMiD”, no. 101054936. There are no additional data beyond that contained within
the main manuscript.\r\nS.D.: Research supported by Taiwan NSTC grants 111-2115-M-002-009-MY2
and 113-2628-M-002-008-MY4.\r\nK.P.: 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. Parts of this research was conducted
while K.P. was at the Department of Computer Science, ETH Zürich, Switzerland, supported
by Swiss National Science Foundation, Switzerland , grant no. CRSII5 173721."
article_number: '104235'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Simona
full_name: Boyadzhiyska, Simona
last_name: Boyadzhiyska
- first_name: Shagnik
full_name: Das, Shagnik
last_name: Das
- first_name: Thomas
full_name: Lesgourgues, Thomas
last_name: Lesgourgues
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
citation:
ama: Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. Odd-Ramsey numbers of complete
bipartite graphs. European Journal of Combinatorics. 2026;131. doi:10.1016/j.ejc.2025.104235
apa: Boyadzhiyska, S., Das, S., Lesgourgues, T., & Petrova, K. H. (2026). Odd-Ramsey
numbers of complete bipartite graphs. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2025.104235
chicago: Boyadzhiyska, Simona, Shagnik Das, Thomas Lesgourgues, and Kalina H Petrova.
“Odd-Ramsey Numbers of Complete Bipartite Graphs.” European Journal of Combinatorics.
Elsevier, 2026. https://doi.org/10.1016/j.ejc.2025.104235.
ieee: S. Boyadzhiyska, S. Das, T. Lesgourgues, and K. H. Petrova, “Odd-Ramsey numbers
of complete bipartite graphs,” European Journal of Combinatorics, vol.
131. Elsevier, 2026.
ista: Boyadzhiyska S, Das S, Lesgourgues T, Petrova KH. 2026. Odd-Ramsey numbers
of complete bipartite graphs. European Journal of Combinatorics. 131, 104235.
mla: Boyadzhiyska, Simona, et al. “Odd-Ramsey Numbers of Complete Bipartite Graphs.”
European Journal of Combinatorics, vol. 131, 104235, Elsevier, 2026, doi:10.1016/j.ejc.2025.104235.
short: S. Boyadzhiyska, S. Das, T. Lesgourgues, K.H. Petrova, European Journal of
Combinatorics 131 (2026).
corr_author: '1'
date_created: 2025-10-16T13:14:34Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-01-05T13:34:48Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104235
ec_funded: 1
external_id:
arxiv:
- '2410.05887'
isi:
- '001573380700001'
file:
- access_level: open_access
checksum: 52883daa217398396cbf9b8ad9ddae92
content_type: application/pdf
creator: dernst
date_created: 2026-01-05T13:34:40Z
date_updated: 2026-01-05T13:34:40Z
file_id: '20954'
file_name: 2026_EuropJourCombinatorics_Boyadzhiyska.pdf
file_size: 563029
relation: main_file
success: 1
file_date_updated: 2026-01-05T13:34:40Z
fulldoi: https://doi.org/10.1016/j.ejc.2025.104235
has_accepted_license: '1'
intvolume: ' 131'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Odd-Ramsey numbers of complete bipartite graphs
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: 131
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '20490'
abstract:
- lang: eng
text: "We study flips in hypertriangulations of planar points sets. Here a level-k
hypertriangulation of n\r\n points in the plane is a subdivision induced by the
projection of a k-hypersimplex, which is the convex hull of the barycenters of
the (k-1)-dimensional faces of the standard (n-1)-simplex. In particular, we introduce
four types of flips and prove that the level-2 hypertriangulations are connected
by these flips.\r\n"
acknowledgement: Work by all authors but the second is supported by the European Research
Council (ERC), grant no. 788183, by the Wittgenstein Prize, Austrian Science Fund
(FWF), grant no. Z 342-N31, and by the DFG Collaborative Research Center TRR 109,
Austrian Science Fund (FWF), grant no. I 02979-N35. Work by the second author is
partially supported by the Alexander von Humboldt Foundation and by the Simons Foundation
. The second author thanks Jesús A. De Loera for useful discussions on flips and
non-flips and Pavel Galashin and Alexey Balitskiy for useful discussions on plabic
graphs.
article_number: '104248'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Alexey
full_name: Garber, Alexey
last_name: Garber
- first_name: Mohadese
full_name: Ghafari, Mohadese
last_name: Ghafari
- first_name: Teresa
full_name: Heiss, Teresa
id: 4879BB4E-F248-11E8-B48F-1D18A9856A87
last_name: Heiss
orcid: 0000-0002-1780-2689
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. Flips in two-dimensional
hypertriangulations. European Journal of Combinatorics. 2026;132. doi:10.1016/j.ejc.2025.104248
apa: Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., & Saghafian, M. (2026).
Flips in two-dimensional hypertriangulations. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2025.104248
chicago: Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafari, Teresa Heiss, and
Morteza Saghafian. “Flips in Two-Dimensional Hypertriangulations.” European
Journal of Combinatorics. Elsevier, 2026. https://doi.org/10.1016/j.ejc.2025.104248.
ieee: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, and M. Saghafian, “Flips
in two-dimensional hypertriangulations,” European Journal of Combinatorics,
vol. 132. Elsevier, 2026.
ista: Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2026. Flips in
two-dimensional hypertriangulations. European Journal of Combinatorics. 132, 104248.
mla: Edelsbrunner, Herbert, et al. “Flips in Two-Dimensional Hypertriangulations.”
European Journal of Combinatorics, vol. 132, 104248, Elsevier, 2026, doi:10.1016/j.ejc.2025.104248.
short: H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, European
Journal of Combinatorics 132 (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2025-10-19T22:01:31Z
date_published: 2026-02-01T00:00:00Z
date_updated: 2026-07-23T11:58:37Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.ejc.2025.104248
ec_funded: 1
external_id:
arxiv:
- '2212.11380'
isi:
- '001599061500002'
fulldoi: https://doi.org/10.1016/j.ejc.2025.104248
intvolume: ' 132'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2212.11380
month: '02'
oa: 1
oa_version: Preprint
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Flips in two-dimensional hypertriangulations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 132
year: '2026'
...
---
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
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: repository
OA_type: green
_id: '19018'
abstract:
- lang: eng
text: "The online semi-random graph process is a one-player game which starts with
the empty graph on n vertices. At every round, a player (called Builder) is presented
with a vertex v chosen uniformly at random and independently from previous rounds,
and constructs an edge of their choice that is incident to v. Inspired by recent
advances on the semi-random graph process, we define a family of generalized online
semi-random models.\r\nWe analyse a particular instance that shares similar features
with the original semi-random graph process and determine the hitting times of
the classical graph properties minimum degree k,k-connectivity, containment of
a perfect matching, a Hamiltonian cycle and an \r\nH-factor for a fixed graph
H possessing an additional tree-like property. Along the way, we derive a few
consequences of the famous Aldous-Broder algorithm that may be of independent
interest."
acknowledgement: We are grateful to Dieter Mitsche for related discussions and to
several anonymous referees for multiple useful comments.
article_number: '104120'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sofiya
full_name: Burova, Sofiya
last_name: Burova
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
citation:
ama: Burova S, Lichev L. The semi-random tree process. European Journal of Combinatorics.
2025;126. doi:10.1016/j.ejc.2025.104120
apa: Burova, S., & Lichev, L. (2025). The semi-random tree process. European
Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104120
chicago: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European
Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104120.
ieee: S. Burova and L. Lichev, “The semi-random tree process,” European Journal
of Combinatorics, vol. 126. Elsevier, 2025.
ista: Burova S, Lichev L. 2025. The semi-random tree process. European Journal of
Combinatorics. 126, 104120.
mla: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” European
Journal of Combinatorics, vol. 126, 104120, Elsevier, 2025, doi:10.1016/j.ejc.2025.104120.
short: S. Burova, L. Lichev, European Journal of Combinatorics 126 (2025).
date_created: 2025-02-10T09:00:53Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2025-09-30T10:28:42Z
day: '01'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104120
external_id:
arxiv:
- '2204.07376 '
isi:
- '001420659400001'
fulldoi: https://doi.org/10.1016/j.ejc.2025.104120
intvolume: ' 126'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2204.07376
month: '05'
oa: 1
oa_version: Preprint
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: The semi-random tree process
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 126
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
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'
...
---
OA_place: repository
OA_type: green
_id: '22181'
abstract:
- lang: eng
text: "A graph G is said to be Ramsey size-linear if r(G, H) = OG(e(H))\r\nfor every
graph H with no isolated vertices. Erdős, Faudree,\r\nRousseau, and Schelp observed
that K4 is not Ramsey size-linear,\r\nbut each of its proper subgraphs is, and
they asked whether there\r\nexist infinitely many such graphs. In this short note,
we answer\r\nthis question in the affirmative"
article_number: '104175'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: Wigderson Y. Infinitely many minimally non-Ramsey size-linear graphs. European
Journal of Combinatorics. 2025;128. doi:10.1016/j.ejc.2025.104175
apa: Wigderson, Y. (2025). Infinitely many minimally non-Ramsey size-linear graphs.
European Journal of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2025.104175
chicago: Wigderson, Yuval. “Infinitely Many Minimally Non-Ramsey Size-Linear Graphs.”
European Journal of Combinatorics. Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104175.
ieee: Y. Wigderson, “Infinitely many minimally non-Ramsey size-linear graphs,” European
Journal of Combinatorics, vol. 128. Elsevier, 2025.
ista: Wigderson Y. 2025. Infinitely many minimally non-Ramsey size-linear graphs.
European Journal of Combinatorics. 128, 104175.
mla: Wigderson, Yuval. “Infinitely Many Minimally Non-Ramsey Size-Linear Graphs.”
European Journal of Combinatorics, vol. 128, 104175, Elsevier, 2025, doi:10.1016/j.ejc.2025.104175.
short: Y. Wigderson, European Journal of Combinatorics 128 (2025).
date_created: 2026-06-29T10:59:47Z
date_published: 2025-08-01T00:00:00Z
date_updated: 2026-07-14T09:13:09Z
day: '01'
doi: 10.1016/j.ejc.2025.104175
extern: '1'
external_id:
arxiv:
- '2409.05931'
fulldoi: https://doi.org/10.1016/j.ejc.2025.104175
intvolume: ' 128'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: 'https://doi.org/10.48550/arXiv.2409.05931 '
month: '08'
oa: 1
oa_version: Preprint
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Infinitely many minimally non-Ramsey size-linear graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 128
year: '2025'
...
---
_id: '9589'
abstract:
- lang: eng
text: We give an asymptotic expression for the expected number of spanning trees
in a random graph with a given degree sequence , provided that the number of edges
is at least , where is the maximum degree. A key part of our argument involves
establishing a concentration result for a certain family of functions over random
trees with given degrees, using Prüfer codes.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Catherine
full_name: Greenhill, Catherine
last_name: Greenhill
- first_name: Mikhail
full_name: Isaev, Mikhail
last_name: Isaev
- 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: Brendan D.
full_name: McKay, Brendan D.
last_name: McKay
citation:
ama: Greenhill C, Isaev M, Kwan MA, McKay BD. The average number of spanning trees
in sparse graphs with given degrees. European Journal of Combinatorics.
2017;63:6-25. doi:10.1016/j.ejc.2017.02.003
apa: Greenhill, C., Isaev, M., Kwan, M. A., & McKay, B. D. (2017). The average
number of spanning trees in sparse graphs with given degrees. European Journal
of Combinatorics. Elsevier. https://doi.org/10.1016/j.ejc.2017.02.003
chicago: Greenhill, Catherine, Mikhail Isaev, Matthew Alan Kwan, and Brendan D.
McKay. “The Average Number of Spanning Trees in Sparse Graphs with given Degrees.”
European Journal of Combinatorics. Elsevier, 2017. https://doi.org/10.1016/j.ejc.2017.02.003.
ieee: C. Greenhill, M. Isaev, M. A. Kwan, and B. D. McKay, “The average number of
spanning trees in sparse graphs with given degrees,” European Journal of Combinatorics,
vol. 63. Elsevier, pp. 6–25, 2017.
ista: Greenhill C, Isaev M, Kwan MA, McKay BD. 2017. The average number of spanning
trees in sparse graphs with given degrees. European Journal of Combinatorics.
63, 6–25.
mla: Greenhill, Catherine, et al. “The Average Number of Spanning Trees in Sparse
Graphs with given Degrees.” European Journal of Combinatorics, vol. 63,
Elsevier, 2017, pp. 6–25, doi:10.1016/j.ejc.2017.02.003.
short: C. Greenhill, M. Isaev, M.A. Kwan, B.D. McKay, European Journal of Combinatorics
63 (2017) 6–25.
date_created: 2021-06-22T12:18:59Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2023-02-23T14:02:00Z
day: '01'
doi: 10.1016/j.ejc.2017.02.003
extern: '1'
external_id:
arxiv:
- '1606.01586'
fulldoi: https://doi.org/10.1016/j.ejc.2017.02.003
intvolume: ' 63'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.ejc.2017.02.003
month: '06'
oa: 1
oa_version: Published Version
page: 6-25
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: The average number of spanning trees in sparse graphs with given degrees
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 63
year: '2017'
...