@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}, } @inproceedings{20007, abstract = {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.}, author = {Anastos, Michael and Kwan, Matthew Alan and Moore, Benjamin}, booktitle = {Proceedings of the 57th Annual ACM Symposium on Theory of Computing}, isbn = {9798400715105}, issn = {0737-8017}, location = {Prague, Czechia}, pages = {2098--2106}, publisher = {Association for Computing Machinery}, title = {{Smoothed analysis for graph isomorphism}}, doi = {10.1145/3717823.3718173}, 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{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{19002, abstract = {A k-subcolouring of a graph G is a function f : V (G) → {0,...,k − 1} such that the set of vertices coloured i induce a disjoint union of cliques. The subchromatic number, χsub(G), is the minimum k such that G admits a k-subcolouring. Nešetril, ˇ Ossona de Mendez, Pilipczuk, and Zhu (2020), recently raised the problem of finding tight upper bounds for χsub(G2) when G is planar. We show that χsub(G2) ≤ 43 when G is planar, improving their bound of 135. We give even better bounds when the planar graph G has larger girth. Moreover, we show that χsub(G3) ≤ 95, improving the previous bound of 364. For these we adapt some recent techniques of Almulhim and Kierstead (2022), while also extending the decompositions of triangulated planar graphs of Van den Heuvel, Ossona de Mendez, Quiroz, Rabinovich and Siebertz (2017), to planar graphs of arbitrary girth. Note that these decompositions are the precursors of the graph product structure theorem of planar graphs. We give improved bounds for χsub(Gp) for all p ≥ 2, whenever G has bounded treewidth, bounded simple treewidth, bounded genus, or excludes a clique or biclique as a minor. For this we introduce a family of parameters which form a gradation between the strong and the weak colouring numbers. We give upper bounds for these parameters for graphs coming from such classes. Finally, we give a 2-approximation algorithm for the subchromatic number of graphs having a layering in which each layer has bounded cliquewidth and this layering is computable in polynomial time (like the class of all dth powers of planar graphs, for fixed d). This algorithm works even if the power p and the graph G is unknown.}, author = {Cortés, Pedro P. and Kumar, Pankaj and Moore, Benjamin and Ossona de Mendez, Patrice and Quiroz, Daniel A.}, issn = {0012-365X}, journal = {Discrete Mathematics}, number = {4}, publisher = {Elsevier}, title = {{Subchromatic numbers of powers of graphs with excluded minors}}, doi = {10.1016/j.disc.2024.114377}, volume = {348}, year = {2025}, } @article{15163, abstract = {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.}, author = {Campbell, Rutger and Hörsch, Florian and Moore, Benjamin}, issn = {0012-365X}, journal = {Discrete Mathematics}, number = {6}, publisher = {Elsevier}, title = {{Decompositions into two linear forests of bounded lengths}}, doi = {10.1016/j.disc.2024.113962}, volume = {347}, year = {2024}, }