Marthe Bonamy, Nicolas Bousquet, Louis Esperet, Carla Groenland, Chun-Hung Liu, Francois Pirot and Alex Scott, Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces, accepted to Journal of the European Mathematical Society.
Asymptotic dimension has been introduced for metric spaces and due to the asymptotic definition, it only makes sense for graph classes or infinite graphs. The following paper determines the asymptotic dimension for various natural graph classes, answering open problems in geometric group theory as a corollary. We also describe connections with algorithmic variants such as weak sparse partition schemes and weak diameter network decompositions.
Carla Groenland, Gwen Joret, Woijech Nadara and Bartek Walczak, Approximating pathwidth for graphs of small treewidth. Journal publication: ACM Transactions on Algorithms, 2023. Conference publication: SODA 2021.
The famous grid minor theorem gives a structural explanation for large treewidth: the graph must contain a large grid as minor. Of course, a graph can have large pathwidth due to having large treewidth. In this paper, we show the only other reason a graph can have large pathwidth, is if it has a large complete binary tree as minor. We provide very tight bounds and exploit the result to give a more efficient algorithm for approximating pathwidth in graphs of small treewidth.
Carla Groenland, Sean Longbrake, Raphael Steiner, Jérémie Turcotte and Liana Yepremyan Longest cycles in vertex-transitive and highly connected graphs, 2025+, Bulletin of the London Mathematical Society.
In the following paper, we provide progress on two old conjectures about longest cycles in graphs: the longest cycle in a vertex-transitive graph and the intersection size of longest cycles in a highly connected graph. Both improvements come from a lemma that is proved via a reformulation to linear programmes that we solve by computer.
Carla Groenland, Tomáš Kaiser, Oscar Treffers and Matthew Wales, Graphs of low average degree without independent transversals. Journal version: Journal of Graph Theory, 102:374-387, 2023.
When the average degree is low, it is easier to find independent transversals and these can be guaranteed with entropy compression related methods such as the Rosenfeld-Wanless-Wood scheme or the Local Cut Lemma. We give an example that shows that, unexpectedly, those lower bounds are tight.
Marthe Bonamy, Carla Groenland, Tom Johnston, Natasha Morrison and Alex Scott, Infinite induced-saturated graphs, arXiv:2506.08810.
It is widely open for which (finite) graphs H there is a (finite) graph G which is H-induced saturated: G does not have an induced copy of H but adding any edge to G or removing any edge from G creates a copy of H. We give a full characterisation in the case in which we allow G to be (countable) infinite. In fact, whenever H is a finite graph that is not a clique or stable set, there is a graph G that has no induced copy of H, but G' has an induced copy of H for any graph G' different from G obtained by changing edges/non-edges such that per vertex only a finite number of incident vertex pairs are adjusted.
Carla Groenland, Jesper Nederlof and Tomohiro Koana, A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a K4-Minor. Conference publication: IPEC 2024.
Steiner tree is the problem of finding a minimum weight spanning tree that contains a given set of terminals. This problem is NP-complete on planar graphs but can be solved in polynomial time when the terminals are all on a single face. In this case, there is no rooted K_4-minor on the terminals. We show that this condition suffices in general: Steiner tree can be solved in polynomial time when there is no rooted K_4-minor on the terminals.
Hans L. Bodlaender, Carla Groenland and Hugo Jacob, List Colouring Trees in Logarithmic Space. Conference publication: ESA 2022.
We expect that List Colouring cannot be solved space efficiently for bounded pathwidth graphs (already for some constant pathwidth). It is therefore a natural question what the space requirements are for trees. We provide a quite involved algorithm to show List Colouring on n-vertex trees can be solved using O(log n) bits of workspace (on a deterministic Turing machine).
Marthe Bonamy, Linda Cook, Carla Groenland and Alexandra Wesolek, A tight local algorithm for the minimum dominating set problem in outerplanar graphs. Conference publication: DISC 2021.
We show that a very simple distributed algorithm is optimal (in terms of its approximation factor in the LOCAL model) for finding a minimum dominating set on outerplanar graphs.
Carla Groenland, Karolina Okrasa, Pawel Rzążewski, Alex Scott, Paul Seymour and Sophie Spirkl, H-colouring Pt-free graphs in subexponential time, Discrete Applied Mathematics, 267:184-189, 2019.
This was the first paper I wrote in my PhD, and it resulted from a merge of joint work with my PhD advisor Alex Scott and work from two other groups of researchers. We show that 3-colouring can be solved in subexponential time if the input graph has no long induced paths. Others have since improved the complexity to quasi-polynomial time, but it remains an interesting open problem whether polynomial time is also possible. We also bound the treedepth of a graph in terms of the longest induced path and maximum degree.
Marthe Bonamy, Carla Groenland, Carole Muller, Jonathan Narboni, Jakub Pekárek and Alexandra Wesolek, A note on connected greedy edge colouring, Discrete Applied Mathematics, 304:129-136, 2021.