Source author record

Rutger Campbell

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

5works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Product structure of graph classes with bounded treewidth

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$ , for every graph ${G \in \mathcal{G}}$ there is a graph $H$ with ${\text{tw}(H) \leq c}$ such that $G$ is isomorphic to a subgraph of ${H \boxtimes K_{f(\text{tw}(G))}}$ . We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of $K_{s,t}$ -minor-free graphs has underlying treewidth $s$ (for ${t \geq \max\{s,3\}}$ ); and the class of $K_t$ -minor-free graphs has underlying treewidth ${t-2}$ . In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.

preprint2019arXiv

On Density-Critical Matroids

For a matroid $M$ having $m$ rank-one flats, the density $d(M)$ is $\tfrac{m}{r(M)}$ unless $m = 0$ , in which case $d(M)= 0$ . A matroid is density-critical if all of its proper minors of non-zero rank have lower density. By a 1965 theorem of Edmonds, a matroid that is minor-minimal among simple matroids that cannot be covered by $k$ independent sets is density-critical. It is straightforward to show that $U_{1,k+1}$ is the only minor-minimal loopless matroid with no covering by $k$ independent sets. We prove that there are exactly ten minor-minimal simple obstructions to a matroid being able to be covered by two independent sets. These ten matroids are precisely the density-critical matroids $M$ such that $d(M) > 2$ but $d(N) \le 2$ for all proper minors $N$ of $M$ . All density-critical matroids of density less than $2$ are series-parallel networks. For $k \ge 2$ , although finding all density-critical matroids of density at most $k$ does not seem straightforward, we do solve this problem for $k=\tfrac{9}{4}$ .

preprint2018arXiv

On a generalisation of spikes

We consider matroids with the property that every subset of the ground set of size $t$ is contained in both an $\ell$ -element circuit and an $\ell$ -element cocircuit; we say that such a matroid has the $(t,\ell)$ -property. We show that for any positive integer $t$ , there is a finite number of matroids with the $(t,\ell)$ -property for $\ell<2t$ ; however, matroids with the $(t,2t)$ -property form an infinite family. We say a matroid is a $t$ -spike if there is a partition of the ground set into pairs such that the union of any $t$ pairs is a circuit and a cocircuit. Our main result is that if a sufficiently large matroid has the $(t,2t)$ -property, then it is a $t$ -spike. Finally, we present some properties of $t$ -spikes.

preprint2016arXiv

Dense PG(n-1,2)-free binary matroids

For each integer $n \geq 2$ , we prove that, if $M$ is a simple rank- $r$ $PG(n-1,2)$ -free binary matroid with $|M|>\left(1-\frac{3}{2^n}\right)2^r$ , then there is a triangle-free corank- $(n-2)$ flat of $M$ .

preprint2015arXiv

On the structure of dense triangle-free binary matroids

We prove, by means of an exact structural description, that every simple triangle-free binary matroid $M$ with $|M| > \tfrac{33}{128}2^{r(M)}$ has critical number at most $2$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.