1 citations · 2 across the 13 of their papers we have counts for
15 papers
Poset dimension and maximum comparability degree
Carla Groenland, Richard Montgomery, Rajko Nenadov +1
In 1986, Füredi and Kahn showed that the dimension of any finite poset satisfies , where is the maximum degree of the comparability graph…
Faster 3-colouring algorithm for graphs of diameter 3
Carla Groenland, Hidde Koerts, Sophie Spirkl
We show that given an -vertex graph of diameter 3 we can decide if is -colourable in time for any . This improves on…
Improved exploration of temporal graphs
Paul Bastide, Carla Groenland, Lukas Michel +2
A temporal graph is a sequence of graphs on the same vertex set of size . The \emph{temporal exploration problem} asks for the length of the shortest seque…
Circular sorting, strong complete mappings and wreath product constructions
Paul Bastide, Anurag Bishnoi, Carla Groenland +2
We continue the study of Adin, Alon and Roichman [arXiv:2502.14398, 2025] on the number of steps required to sort labelled points on a circle by transpositions. Imagine that th…
Smaller universal posets
Paul Bastide, Carla Groenland, Rajko Nenadov
We show that there is a constant such that for each integer , there is a poset on at most elements that contains each -element poset as an (i…
Note on extremal problems about connected subgraph sums
Stijn Cambie, Carla Groenland
For a graph with vertex assignment , we define for a connected subgraph of as a connected subgraph sum of . We study t…
Faithful universal graphs for minor-closed classes
Paul Bastide, Louis Esperet, Carla Groenland +3
It was proved by Huynh, Mohar, Šámal, Thomassen and Wood in 2021 that any countable graph containing every countable planar graph as a subgraph has an infinite clique minor. We pro…
Quasi-linear distance query reconstruction for graphs of bounded treelength
Paul Bastide, Carla Groenland
In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices and ,…
A Polynomial Time Algorithm for Steiner Tree when Terminals Avoid a -Minor
Carla Groenland, Jesper Nederlof, Tomohiro Koana
We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a termi…
Longest cycles in vertex-transitive and highly connected graphs
Carla Groenland, Sean Longbrake, Raphael Steiner +2
We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively,…
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Rank Parameters
Carla Groenland, Isja Mannens, Jesper Nederlof +2
A homomorphism from a graph to a graph is an edge-preserving mapping from to . In the graph homomorphism problem, denoted by , the graph is fixed a…
Optimal distance query reconstruction for graphs without long induced cycles
Paul Bastide, Carla Groenland
Given access to the vertex set of a connected graph and an oracle that given two vertices , returns the shortest path distance between and , how many…
Reconstructing Graphs from Connected Triples
Paul Bastide, Linda Cook, Jeff Erickson +4
We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In…
Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
Carla Groenland, Jesper Nederlof, Isja Mannens +1
We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decomposit…
Graphs of low average degree without independent transversals
Carla Groenland, Tomáš Kaiser, Oscar Treffers +1
An independent transversal of a graph with a vertex partition is an independent set of intersecting each block of in a single vertex. Wanless and…