@article{20482, abstract = {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.}, author = {Boyadzhiyska, Simona and Das, Shagnik and Lesgourgues, Thomas and Petrova, Kalina H}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Odd-Ramsey numbers of complete bipartite graphs}}, doi = {10.1016/j.ejc.2025.104235}, volume = {131}, year = {2026}, } @article{19879, abstract = {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.}, author = {Dvořák, Zdeněk and Moore, Benjamin and Seifrtová, Michaela and Šámal, Robert}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Precoloring extension in planar near-Eulerian-triangulations}}, doi = {10.1016/j.ejc.2025.104138}, volume = {127}, year = {2025}, } @article{20320, abstract = {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 theorem 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 d ≡ 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 extension 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.}, author = {Mies, Sebastian and Moore, Benjamin and Smith-Roberge, Evelyne}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, number = {12}, publisher = {Elsevier}, title = {{Beyond the pseudoforest strong Nine Dragon Tree theorem}}, doi = {10.1016/j.ejc.2025.104214}, volume = {130}, year = {2025}, } @article{20490, abstract = {We study flips in hypertriangulations of planar points sets. Here a level-k hypertriangulation of 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. }, author = {Edelsbrunner, Herbert and Garber, Alexey and Ghafari, Mohadese and Heiss, Teresa and Saghafian, Morteza}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{Flips in two-dimensional hypertriangulations}}, doi = {10.1016/j.ejc.2025.104248}, volume = {132}, year = {2025}, } @article{18753, abstract = {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 such that H -free digraphs in C have bounded dichromatic number. We show that if F 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.}, author = {Carbonero, Alvaro and Koerts, Hidde and Moore, Benjamin and Spirkl, Sophie}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{On heroes in digraphs with forbidden induced forests}}, doi = {10.1016/j.ejc.2024.104104}, volume = {125}, year = {2025}, } @article{19018, abstract = {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. We 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 H-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.}, author = {Burova, Sofiya and Lichev, Lyuben}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, publisher = {Elsevier}, title = {{The semi-random tree process}}, doi = {10.1016/j.ejc.2025.104120}, volume = {126}, year = {2025}, } @article{9589, abstract = {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.}, author = {Greenhill, Catherine and Isaev, Mikhail and Kwan, Matthew Alan and McKay, Brendan D.}, issn = {0195-6698}, journal = {European Journal of Combinatorics}, pages = {6--25}, publisher = {Elsevier}, title = {{The average number of spanning trees in sparse graphs with given degrees}}, doi = {10.1016/j.ejc.2017.02.003}, volume = {63}, year = {2017}, }