Nick Brettell

activity

20152026

most citedColouring graphs with constraints on connectivity

13 citations · 95 across the 28 of their papers we have counts for

collaborators

31 papers

math.CO2026

The excluded minors for $Z_{3}$ -gainable and regular biased graphs

Nick Brettell, Rutger Campbell, Daryl Funk +1

We prove that a biased graph is gainable over the group $Z_{3}$ if and only if it contains no minor isomorphic to $(4 K_{2}, \emptyset)$ , $\pm K_{3}$ , or $- K_{4}$ . We develo…

math.CO2026

A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k

Sam Bastida, Nick Brettell

For a graph $G$ with at least two vertices, the maximum local edge-connectivity of $G$ is the maximum number of edge-disjoint $(u, v)$ -paths over all distinct pairs of vertices $(u,…

math.CO2025

The excluded minors of the class of spike minors

Sam Bastida, Nick Brettell, Rutger Campbell +4

Mayhew et al.\ (2021) posed the problem of showing that the minor-closed class of spikes and their minors has a finite set of excluded minors and describing all of them. In this pa…

cs.CC2025

Non-crossing $H$ -graphs: a generalization of proper interval graphs admitting FPT algorithms

Flavia Bonomo-Braberman, Nick Brettell, Noleen Köhler +2

We prove new parameterized complexity results for the FO Model Checking problem on a well-known generalization of interval and circular-arc graphs: the class of $H$ -graphs, for any…

math.CO2024

Detachable pairs in $3$ -connected matroids and simple $3$ -connected graphs

Nick Brettell, Charles Semple, Gerry Toft

Let $M$ be a $3$ -connected matroid. A pair ${e, f}$ in $M$ is detachable if $M \ e \ f$ or $M / e / f$ is $3$ -connected. Williams (2015) proved that if $M$ has a…

math.CO2024

Clonal cores and flexipaths in matroids

Nick Brettell, James Oxley, Charles Semple +1

A partitioned matroid $(M, {X_{1}, X_{2}, \dots, X_{n}})$ consists of a matroid $M$ and a partition ${X_{1}, X_{2}, \dots, X_{n}}$ of its ground set. As such structures arise frequently in struc…

math.CO2023★ 1 cited

What is a 4-connected matroid?

Nick Brettell, Susan Jowett, James Oxley +2

The {\em breadth} of a tangle $T$ in a matroid is the size of the largest spanning uniform submatroid of the tangle matroid of $T$ . A matroid $M$ is {\em weakly…

math.CO2023

Comparing Width Parameters on Graph Classes

Nick Brettell, Andrea Munaro, Daniël Paulusma +1

We study how the relationship between non-equivalent width parameters changes once we restrict to some special graph class. As width parameters, we consider treewidth, clique-width…

math.CO2023★ 1 cited

The excluded minors for GF(5)-representable matroids on ten elements

Nick Brettell

Mayhew and Royle (2008) showed that there are 564 excluded minors for the class of GF(5)-representable matroids having at most 9 elements. We enumerate the excluded minors for GF(5…

math.CO2023

Computing Subset Vertex Covers in $H$ -Free Graphs

Nick Brettell, Jelle J. Oostveen, Sukanya Pandey +3

We consider a natural generalization of Vertex Cover: the Subset Vertex Cover problem, which is to decide for a graph $G = (V, E)$ , a subset $T \subseteq V$ and integer $k$ , if $V$ has…

math.CO2023★ 3 cited

Computing excluded minors for classes of matroids representable over partial fields

Nick Brettell, Rudi Pendavingh

We describe an implementation of a computer search for the "small" excluded minors for a class of matroids representable over a partial field. Using these techniques, we enumerate…

math.CO2022

Generalized spikes with circuits and cocircuits of different cardinalities

Nick Brettell, Kevin Grace

We consider matroids with the property that every subset of the ground set of size $s$ is contained in a $2 s$ -element circuit and every subset of size $t$ is contained in a $2 t$ -el…

math.CO2022★ 7 cited

The excluded minors for 2- and 3-regular matroids

Nick Brettell, James Oxley, Charles Semple +1

The class of 2-regular matroids is a natural generalisation of regular and near-regular matroids. We prove an excluded-minor characterisation for the class of 2-regular matroids. T…

math.CO2022★ 3 cited

Excluded minors are almost fragile II: essential elements

Nick Brettell, James Oxley, Charles Semple +1

Let $M$ be an excluded minor for the class of $P$ -representable matroids for some partial field $P$ , let $N$ be a $3$ -connected strong $P$ -stabilizer tha…

math.CO2021

Cyclic matroids

Nick Brettell, Charles Semple, Gerry Toft

For all positive integers $s$ and $t$ exceeding one, a matroid $M$ on $n$ elements is {\em nearly $(s, t)$ -cyclic} if there is a cyclic ordering $σ$ of its ground set such that eve…

cs.DS2020★ 9 cited

Solving Problems on Generalized Convex Graphs via Mim-Width

Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro +1

A bipartite graph $G = (A, B, E)$ is $H$ -convex, for some family of graphs $H$ , if there exists a graph $H \in H$ with $V (H) = A$ such that the set of neighbours in $…

cs.DS2020★ 10 cited

List $k$ -Colouring $P_{t}$ -Free Graphs: a Mim-width Perspective

Nick Brettell, Jake Horsfield, Andrea Munaro +1

A colouring of a graph $G = (V, E)$ is a mapping $c : V \to {1, 2, \dots}$ such that $c (u) \neq = c (v)$ for every two adjacent vertices $u$ and $v$ of $G$ . The {\sc List $k$ -Colourin…

cs.DS2020

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

Benjamin Bergougnoux, Édouard Bonnet, Nick Brettell +1

The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time $2^{O (tw)} n^{O (1)}$ , for F…

cs.DS2020

Computing Weighted Subset Transversals in $H$ -Free Graphs

Nick Brettell, Matthew Johnson, Daniel Paulusma

For the Odd Cycle Transversal problem, the task is to find a small set $S$ of vertices in a graph that intersects every cycle of odd length. The Subset Odd Cycle Transversal proble…

cs.DS2020

Colouring $(s P_{1} + P_{5})$ -Free Graphs: a Mim-Width Perspective

Nick Brettell, Jake Horsfield, Daniel Paulusma

We prove that the class of $(K_{t}, s P_{1} + P_{5})$ -free graphs has bounded mim-width for every $s \geq 0$ and $t \geq 1$ , and that there is a polynomial-time algorithm that, given a graph i…

cs.DS2020

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective

Hans Bodlaender, Nick Brettell, Matthew Johnson +3

We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced…

cs.DS2020★ 12 cited

Bounding the Mim-Width of Hereditary Graph Classes

Nick Brettell, Jake Horsfield, Andrea Munaro +2

A large number of NP-hard graph problems become polynomial-time solvable on graph classes where the mim-width is bounded and quickly computable. Hence, when solving such problems o…

math.CO2018★ 2 cited

Matroids with a cyclic arrangement of circuits and cocircuits

Nick Brettell, Deborah Chun, Tara Fife +1

For all positive integers $t$ exceeding one, a matroid has the cyclic $(t - 1, t)$ -property if its ground set has a cyclic ordering $σ$ such that every set of $t - 1$ consecutive elemen…

math.CO2018★ 6 cited

$N$ -detachable pairs in 3-connected matroids III: the theorem

Nick Brettell, Geoff Whittle, Alan Williams

Let $M$ be a 3-connected matroid, and let $N$ be a 3-connected minor of $M$ . A pair ${x_{1}, x_{2}} \subseteq E (M)$ is $N$ -detachable if one of the matroids $M / x_{1} / x_{2}$ or $M \backsla…

The excluded minors for Z3​-gainable and regular biased graphs

A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k

The excluded minors of the class of spike minors

Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms

Detachable pairs in 3-connected matroids and simple 3-connected graphs

Clonal cores and flexipaths in matroids

What is a 4-connected matroid?

Comparing Width Parameters on Graph Classes

The excluded minors for GF(5)-representable matroids on ten elements

Computing Subset Vertex Covers in H-Free Graphs

Computing excluded minors for classes of matroids representable over partial fields

Generalized spikes with circuits and cocircuits of different cardinalities

The excluded minors for 2- and 3-regular matroids

Excluded minors are almost fragile II: essential elements

Cyclic matroids

Solving Problems on Generalized Convex Graphs via Mim-Width

List k-Colouring Pt​-Free Graphs: a Mim-width Perspective

Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth

Computing Weighted Subset Transversals in H-Free Graphs

Colouring (sP1​+P5​)-Free Graphs: a Mim-Width Perspective

Steiner Trees for Hereditary Graph Classes: a Treewidth Perspective

Bounding the Mim-Width of Hereditary Graph Classes

Matroids with a cyclic arrangement of circuits and cocircuits

N-detachable pairs in 3-connected matroids III: the theorem

The excluded minors for $Z_{3}$ -gainable and regular biased graphs

Non-crossing $H$ -graphs: a generalization of proper interval graphs admitting FPT algorithms

Detachable pairs in $3$ -connected matroids and simple $3$ -connected graphs

Computing Subset Vertex Covers in $H$ -Free Graphs

List $k$ -Colouring $P_{t}$ -Free Graphs: a Mim-width Perspective

Computing Weighted Subset Transversals in $H$ -Free Graphs

Colouring $(s P_{1} + P_{5})$ -Free Graphs: a Mim-Width Perspective

$N$ -detachable pairs in 3-connected matroids III: the theorem