# Wouter | Cames van Batenburg

As of August 2021, I am a postdoctoral researcher at the Delft Institute of Applied Mathematics (TU Delft), The Netherlands. My main research interests are in graph theory and combinatorics. In particular: colouring problems and extremal combinatorics on graphs. Before Delft, I worked in Grenoble, Brussels and Nijmegen. Here is a list of my papers on arXiv.

## E-mail

• w.p.s.camesvanbatenburg (at) tudelft (dot) nl

## Preprints

• S. Cambie, W. Cames van Batenburg and D. Cranston. Optimally Reconfiguring List and Correspondence Colourings. 18pp. (2022+).
|slides|
Abstract

The reconfiguration graph $C_k(G)$ for the $k$-colourings of a graph $G$ has a vertex for each proper $k$-colouring of $G$, and two vertices of $C_k(G)$ are adjacent precisely when those $k$-colourings differ on a single vertex of $G$. Much work has focused on bounding the maximum value of the diameter of $(C_k(G))$ over all $n$-vertex graphs $G$. We consider the analogous problems for list colourings and for correspondence colourings.

We conjecture that if $L$ is a list-assignment for a graph $G$ with $|L(v)|\ge d(v)+2$ for all $v\in V(G)$, then diameter$(C_L(G))\le n(G)+\mu(G)$, where $\mu(G)$ denotes the matching number of $G$. We also conjecture that if $(L,H)$ is a correspondence cover for a graph $G$ with $|L(v)|\ge d(v)+2$ for all $v\in V(G)$, then diam $C_{(L,H)}(G)\le n(G)+\tau(G)$, where $\tau(G)$ denotes the vertex cover number of $G$.

• S. Cambie, W. Cames van Batenburg, E. Davies and R.J. Kang. Packing list-colourings. 31pp. (2021+).
|slides| |extended abstract|
Abstract

List colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a $k$-list-assignment $L$ of a graph $G$, which is the assignment of a list $L(v)$ of $k$ colours to each vertex $v\in V(G)$, we study the existence of $k$ pairwise-disjoint proper colourings of $G$ using colours from these lists. We may refer to this as a list-packing. Correspondingly, we define the list-packing number of $G$ as the smallest $k$ for which a list-packing is guaranteed to exist for every $k$-list-assignment of $G$.

Using a mix of combinatorial and probabilistic methods (with a central role for random binary matrices), we set out some basic upper bounds on the list-packing number, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of $G$. We also pursue a more focused study of the case when $G$ is a bipartite graph.

Our results do not yet rule out the tantalising prospect that the list-packing number is uniformly bounded by a constant multiple of the list chromatic number.

Our study has taken inspiration from study of the strong chromatic number, and we also explore generalisations of the problem above in the same spirit, such as a packing variant of the correspondence chromatic number. For instance, we find that the correspondence packing number (and hence the list-packing number) of a bipartite graph with maximum degree $\Delta$ is at most $(1+o(1)) \Delta/\log \Delta$, which is sharp up to a factor at most two.

## Publications

• W. Cames van Batenburg. Minimum maximal matchings in cubic graphs. The Electronic Journal of Combinatorics, 29(2): P2.36. (2022).
Abstract

We prove that every connected cubic graph with $n$ vertices has a maximal matching of size at most $\frac{5}{12} n+ \frac{1}{2}$. This confirms the cubic case of a conjecture of Baste, Fürst, Henning, Mohr and Rautenbach (2019) on regular graphs. More generally, we prove that every graph with $n$ vertices and $m$ edges and maximum degree at most $3$ has a maximal matching of size at most $\frac{4n-m}{6}+ \frac{1}{2}$. These bounds are attained by the graph $K_{3,3}$, but asymptotically there may still be some room for improvement. Moreover, the claimed maximal matchings can be found efficiently. As a corollary, we have a $\left(\frac{25}{18} + O \left( \frac{1}{n}\right)\right)$-approximation algorithm for minimum maximal matching in connected cubic graphs.

• S. Cambie, W. Cames van Batenburg, R. de Joannis de Verclos and R.J. Kang. Maximising line subgraphs of diameter at most $t$. SIAM Journal on Discrete Mathematics, Volume 36, Issue 2. (2022).
Abstract

We wish to bring attention to a natural but slightly hidden problem, posed by Erdős and Nešetřil. in the late 1980s, an edge version of the degree-diameter problem. Our main result is that, for any graph of maximum degree $\Delta$ with more than $1.5\Delta^t$ edges, its line graph must have diameter larger than $t$. In the case where the graph contains no cycle of length $2t+1$, we can improve the bound on the number of edges to one that is exact for $t \in \left\{1,2,3,4,6\right\}$. In the case $\Delta=3$ and $t=3$, we obtain an exact bound. Our results also have implications for the related problem of bounding the distance-$t$ chromatic index, $t>2$; in particular, for this we obtain an upper bound of $1.941 \Delta^t$ for graphs of large enough maximum degree $\Delta$, markedly improving upon earlier bounds for this parameter.

• W. Cames van Batenburg, R. de Joannis de Verclos, R.J. Kang and F. Pirot. Strong chromatic index and Hadwiger number. Journal of Graph Theory 100: 435–457. (2022).
Abstract

We investigate the effect of a fixed forbidden clique minor upon the strong chromatic index, both in multigraphs and in simple graphs. We conjecture for each $k\ge 4$ that any $K_k$-minor-free multigraph of maximum degree $\Delta$ has strong chromatic index at most $\frac32(k-2)\Delta$. We present a construction certifying that if true the conjecture is asymptotically sharp as $\Delta\to\infty$. In support of the conjecture, we show it in the case $k=4$ and prove the statement for strong clique number in place of strong chromatic index. By contrast, we make a basic observation that for $K_k$-minor-free simple graphs, the problem of strong edge-colouring is between'' Hadwiger's Conjecture and its fractional relaxation. We also treat $K_k$-minor-free multigraphs of edge-diameter at most $2$.

• N.R. Aravind, S. Cambie, W. Cames van Batenburg, R. de Joannis de Verclos, R.J. Kang and V. Patel. Chromatic structure in triangle-free graphs. The Electronic Journal of Combinatorics, 28(2): P2.47. (2021).
Abstract

Motivated by a conjecture of the first author, we prove that every properly coloured triangle-free graph of chromatic number $\chi$ contains a rainbow independent set of size $\lceil\frac12\chi\rceil$. This is sharp up to a factor $2$. This result and its short proof have implications for the related notion of chromatic discrepancy. Drawing inspiration from both structural and extremal graph theory, we conjecture that every triangle-free graph of chromatic number $\chi$ contains an induced cycle of length $\Omega(\chi\log\chi)$ as $\chi\to\infty$. Even if we only asked for an induced path of length $\Omega(\chi\log\chi)$, the conclusion would be sharp up to a constant multiple. We prove it for regular girth $5$ graphs and for girth $21$ graphs. As a common strengthening of the induced paths form of this conjecture and of Johansson's theorem (1996), we posit the existence of some $c>0$ such that for every forest $H$ on $D$ vertices, every triangle-free and induced H-free graph has chromatic number at most $\frac{cD}{\log D}$. We prove this assertion with triangle-free replaced by regular girth $5$.

• N. Bousquet, W. Cames van Batenburg, L. Esperet, G. Joret, W. Lochet, C. Muller and F. Pirot. Packing and covering balls in graphs excluding a minor. Combinatorica, 41(1). (2021).
|talk by co-author|
Abstract

We prove that for every integer $t\ge 1$ there exists a constant $c_t$ such that for every $K_t$-minor-free graph $G$ and every set $S$ of balls in $G$, the minimum size of a set of vertices of $G$ intersecting all the balls of $S$ is at most $c_t$ times the maximum number of vertex-disjoint balls in $S$. This was conjectured by Chepoi, Estellon, and Vaxès in 2007 in the special case of planar graphs and of balls having the same radius.

• W. Cames van Batenburg, G. Joret and A. Ulmer. Erdős-Pósa from ball packing. SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, pages 1609-1619. (2020)
|slides|
Abstract

A classic theorem of Erdős and Pósa (1965) states that every graph has either $k$ vertex-disjoint cycles or a set of $O(k \log k)$ vertices meeting all its cycles. While the standard proof revolves around finding a large `frame' in the graph (a subdivision of a large cubic graph), an alternative way of proving this theorem is to use a ball packing argument of Kühn and Osthus (2003) and Diestel and Rempel (2005). In this paper, we argue that the latter approach is particularly well suited for studying edge variants of the Erdős-Pósa theorem.

As an illustration, we give a short proof of a theorem of Bruhn, Heinlein, and Joos (2019), that cycles of length at least $\ell$ have the so-called edge-Erdős-Pósa property. More precisely, we show that every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ or an edge set $F$ of size $O(k\ell \cdot \log (k\ell))$ such that $G-F$ has no cycle of length at least $\ell$. For fixed $\ell$, this improves on the previously best known bound of $O(k^2 \log k +k\ell)$.

• W. Cames van Batenburg, J. Goedgebeur and G. Joret. Large independent sets in triangle-free cubic graphs: beyond planarity. Advances in Combinatorics, 2020:7, 45pp.
|slides|
Abstract

Every $n$-vertex planar triangle-free graph with maximum degree at most $3$ has an independent set of size at least $\frac{3}{8}n$. This was first conjectured by Albertson, Bollob\'as and Tucker, and was later proved by Heckman and Thomas. Fraughnaugh and Locke conjectured that the planarity requirement could be relaxed into just forbidding a few specific nonplanar subgraphs: They described a family $\mathcal{F}$ of six nonplanar graphs (each of order at most $22$) and conjectured that every $n$-vertex triangle-free graph with maximum degree at most $3$ having no subgraph isomorphic to a member of $\mathcal{F}$ has an independent set of size at least $\frac{3}{8}n$.

In this paper, we prove this conjecture. As a corollary, we obtain that every $2$-connected $n$-vertex triangle-free graph with maximum degree at most $3$ has an independent set of size at least $\frac{3}{8}n$, with the exception of the six graphs in $\mathcal{F}$. This confirms a conjecture made independently by Bajnok and Brinkmann, and by Fraughnaugh and Locke.

• W. Cames van Batenburg, R. de Joannis de Verclos, R.J. Kang and F. Pirot. Bipartite induced density in triangle-free graphs. The Electronic Journal of Combinatorics, 27(2): P2.34. (2020).
Abstract

We prove that any triangle-free graph on $n$ vertices with minimum degree at least $d$ contains a bipartite induced subgraph of minimum degree at least $d^2/(2n)$. This is sharp up to a logarithmic factor in $n$. Relatedly, we show that the fractional chromatic number of any such triangle-free graph is at most the minimum of $n/d$ and $(2+o(1))\sqrt{n/\log n}$ as $n\to\infty$. This is sharp up to constant factors. Similarly, we show that the list chromatic number of any such triangle-free graph is at most $O(\min\{\sqrt{n},(n\log n)/d\})$ as $n\to\infty$.

Relatedly, we also make two conjectures. First, any triangle-free graph on $n$ vertices has fractional chromatic number at most $(\sqrt{2}+o(1))\sqrt{n/\log n}$ as $n\to\infty$. Second, any triangle-free graph on $n$ vertices has list chromatic number at most $O(\sqrt{n/\log n})$ as $n\to\infty$.

• W. Cames van Batenburg, R.J. Kang and F. Pirot. Strong cliques and forbidden cycles. Indagationes Mathematicae, 31(1): pages 64-82 (2020)
Abstract

Given a graph $G$, the strong clique number $\omega_2'(G)$ of $G$ is the cardinality of a largest collection of edges every pair of which are incident or connected by an edge in $G$. We study the strong clique number of graphs missing some set of cycle lengths. For a graph $G$ of large enough maximum degree $\Delta$, we show among other results the following:

$\omega_2'(G)\le5\Delta^2/4$ if $G$ is triangle-free;
$\omega_2'(G)\le3(\Delta-1)$ if $G$ is $C_4$-free;
$\omega_2'(G)\le\Delta^2$ if $G$ is $C_{2k+1}$-free for some $k\ge 2$.

These bounds are attained by natural extremal examples. Our work extends and improves upon previous work of Faudree, Gy\'arf\'as, Schelp and Tuza (1990), Mahdian (2000) and Faron and Postle (2019). We are motivated by the corresponding problems for the strong chromatic index.

• W. Cames van Batenburg, T. Huynh, G. Joret and J.-F. Raymond. A tight Erdős-Pósa function for planar minors. Advances in Combinatorics, 2019:2, 33pp. Extended abstract in proc. of SODA 2019.
Abstract

Let $H$ be a planar graph. By a classical result of Robertson and Seymour, there is a function $f:\mathbb{N} \to \mathbb{R}$ such that for all $k \in \mathbb{N}$ and all graphs $G$, either $G$ contains $k$ vertex-disjoint subgraphs each containing $H$ as a minor, or there is a subset $X$ of at most $f(k)$ vertices such that $G-X$ has no $H$-minor. We prove that this remains true with $f(k) = c k \log k$ for some constant $c=c(H)$. This bound is best possible, up to the value of $c$, and improves upon a recent result of Chekuri and Chuzhoy (STOC 2013), who established this with $f(k) = c k \log^d k$ for some universal constant $d$. The proof is constructive and yields a polynomial-time $O(\log \text{opt})$-approximation algorithm for packing subgraphs containing an $H$-minor.

• W. Cames van Batenburg and R.J. Kang. Squared chromatic number without claws or large cliques. Canadian Mathematical Bulletin, 62(1), pages 23-35. (2019)
Abstract

Let $G$ be a claw-free graph on $n$ vertices with clique number $\omega$, and consider the chromatic number $\chi(G^2)$ of the square $G^2$ of $G$. Writing $\chi_s^{'}(d)$ for the supremum of $\chi(L^2)$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $\chi(G^2) \leq \chi_s^{'}(\omega)$ for $\omega \in \left\{3,4\right\}$. For $\omega=3$, this implies the sharp bound $\chi(G^2) \leq 10$. For $\omega=4$, this implies $\chi(G^2) \leq 22$, which is within $2$ of the conjectured best bound. This work is motivated by a strengthened form of a conjecture of Erdős and Nešetřil.

• W. Cames van Batenburg and R.J. Kang. Packing graphs of bounded codegree. Combinatorics, Probability and Computing, Volume 27, Issue 5, 13pp. (2018)
Abstract

Two graphs $G_1$ and $G_2$ on $n$ vertices are said to pack if there exist injective mappings of their vertex sets into $[n]$ such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollob\'as and Eldridge and, independently, Catlin, asserts that, if $(\Delta(G_1)+1) (\Delta(G_2)+1) \le n+1$, then $G_1$ and $G_2$ pack. We consider the validity of this assertion under the additional assumption that $G_1$ or $G_2$ has bounded codegree. In particular, we prove for all $t \ge 2$ that, if $G_1$ contains no copy of the complete bipartite graph $K_{2,t}$ and $\Delta(G_1) > 17 t \cdot \Delta(G_2)$, then $(\Delta(G_1)+1) (\Delta(G_2)+1) \le n+1$ implies that $G_1$ and $G_2$ pack. We also provide a mild improvement if moreover $G_2$ contains no copy of the complete tripartite graph $K_{1,1,s}$, $s\ge 1$.

• W. Cames van Batenburg, L. Esperet and T. Müller. Coloring Jordan regions and curves. SIAM Journal on Discrete Mathematics, Volume 31, Issue 3, pages 1670-1684. (2017)
Abstract

A Jordan region is a subset of the plane that is homeomorphic to a closed disk. Consider a family $\mathcal{F}$ of Jordan regions whose interiors are pairwise disjoint, and such that any two Jordan regions intersect in at most one point. If any point of the plane is contained in at most $k$ elements of $\mathcal{F}$ (with $k$ sufficiently large), then we show that the elements of $\mathcal{F}$ can be colored with at most $k+1$ colors so that intersecting Jordan regions are assigned distinct colors. This is best possible and answers a question raised by Reed and Shepherd in $1996$. As a simple corollary, we also obtain a positive answer to a problem of Hliněný ($1998$) on the chromatic number of contact systems of strings. We also investigate the chromatic number of families of touching Jordan curves. This can be used to bound the ratio between the maximum number of vertex-disjoint directed cycles in a planar digraph, and its fractional counterpart.

• W. Cames van Batenburg. The dimension of the incipient infinite cluster. Electron. Commun. Probab. Volume 20, paper no. 33., 10pp. (2015)
Abstract

We study the Incipient Infinite Cluster (IIC) of high-dimensional bond percolation on $\mathbb{Z}^d$. We prove that the mass dimension of IIC almost surely equals $4$ and the volume growth exponent of IIC almost surely equals $2$.

## Other

• W. Cames van Batenburg and R.J. Kang. The Bollobás-Eldridge-Catlin conjecture for even girth at least 10. 10pp. (not submitted because we obtained a simpler proof afterwards)
• W. Cames van Batenburg, A. Czechowski, J. van den Leer Duran, B. Lindenhovius and E. Siero. Frequency decompositions in autoregression models. For the Dutch Study Group Mathematics with Industry 2016, 13pp.

## Teaching

At Université Libre de Bruxelles, I lectured for the following courses:

• 2020, Graphs and Networks
• November 2019, Graphs and Networks

As a student at Leiden University (until 2013) and then as a PhD student at Radboud University (until 2017), I have taught exercise classes for the following courses:

• Autumn 2017 and Autumn 2016, Advanced Probability.
• Spring 2017, Game theory.
• Spring 2016 and Spring 2015, Inleiding Kansrekening (Introduction to probability theory).
• Autumn 2015, Autumn 2014 and Spring 2014, Applied Stochastics (Random graphs and Ramsey theory).
• Autumn 2012 and Autumn 2010, Analyse 1 (Calculus).
• Spring 2011, Analyse 4 (Complex analysis).
• Spring 2010, Analyse 2 (Advanced calculus).
• Autumn 2010, Calculus A (Basic calculus for the Biopharmaceutical Sciences).

## Fun fact

My public Algorand wallet address currently is mathematics.algo. Therefore this website can also be reached via https://mathematics.algo.xyz

## Collaborators

N.R. Aravind, Nicolas Bousquet, Stijn Cambie, Daniel Cranston, Ewan Davies, Louis Esperet, Jan Goedgebeur, Rémi de Joannis de Verclos, Gwenaël Joret, Tony Huynh, Ross J. Kang, William Lochet, Carole Muller, Tobias Müller, Viresh Patel, François Pirot, Jean-Florent Raymond, Arthur Ulmer, Xiaochen Y. Zheng.

Last update: April, 2022