Tuesday, April 5, 3pm ET (8pm BST, *7am* Wed NZST)
Lise Turner, University of Waterloo
A local version of Hadwiger’s Conjecture

Abstract:

In 1943, Hadwiger famously conjectured that graphs with no $K_t$ minors are $t-1$ colourable. There has also been significant interest in several variants of the problem, such as list colouring or only forbidding certain classes of minors. We propose a local version where all balls of radius $O(\log v(G))$ must be $K_t$-minor free but the graph as a whole may not be. We prove list colouring results for these graphs equivalent to the best known results for $K_t$-minor free graphs for $t\leq 5$ and large $t$. In the process, we provide some efficient distributed algorithms for finding such colourings.

Joint work with Benjamin Moore and Luke Postle.

Tuesday, March 29, 3pm ET (8pm GMT, 8am Wed NZDT)
Zishen Qu, University of Waterloo
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs

Abstract:

Finding sufficient conditions for a class of graphs to be Hamiltonian is an old problem, with a wide variety of conditions such as Dirac’s degree condition and Whitney’s theorem on 4-connected planar triangulations. We discuss some past results on sufficient conditions for Hamiltonicity involving the exclusion of fixed induced subgraphs, and some properties of the graphs involved in such results. In 1981 Duffus, Gould, and Jacobson showed that any connected graph that does not contain a claw or a net as an induced subgraph has a Hamiltonian path. We aim to find an analogous result for Hamiltonian cycles. In particular, we would like to find a set of graphs $S$ which are 2-connected, non-Hamiltonian, and every proper 2-connected induced subgraph is Hamiltonian such that every 2-connected $S$-free graph is Hamiltonian. In joint work with Joseph Cheriyan, Sepehr Hajebi, and Sophie Spirkl, we show that the classes of 2-connected split graphs and 2-connected triangle-free graphs can be characterised in this fashion.

Tuesday, March 22, 5pm ET (*9pm* GMT, *10am* Wed NZDT)
O-joung Kwon, Hanyang University
Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)

Abstract:

In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé and Watrigant [J. ACM 2022] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced $f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced bandwidth, which implies and is stronger than bounded twin-width (reduced maximum degree). We show that every proper minor-closed class has bounded reduced bandwidth, which is qualitatively stronger than an analogous result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. Furthermore, we separate twin-width and reduced bandwidth by showing that any infinite class of expanders excluding a fixed complete bipartite subgraph has unbounded reduced bandwidth, while there are bounded-degree expanders with twin-width at most 6. This is joint work with Édouard Bonnet and David Wood.

Tuesday, March 15, 3pm ET (*7pm* GMT, *8am* Wed NZDT)
Ahmad Abdi, LSE
On packing dijoins in digraphs and weighted digraphs

Abstract:

Let $D=(V,A)$ be a digraph. A dicut is the set of arcs in a cut where all the arcs cross in the same direction, and a dijoin is a set of arcs whose contraction makes $D$ strongly connected. It is known that every dicut and dijoin intersect. Suppose every dicut has size at least $k$.

Woodall’s Conjecture, an important open question in Combinatorial Optimization, states that there exist $k$ pairwise disjoint dijoins. We make a step towards resolving this conjecture by proving that $A$ can be decomposed into two sets $A_1$ and $A_2$, where $A_1$ is a dijoin, and $A_2$ intersects every dicut in at least $k-1$ arcs. We prove this by a Decompose, Lift, and Reduce (DLR) procedure, in which $D$ is turned into a sink-regular $(k,k+1)$-bipartite digraph. From there, by an application of Matroid Optimization tools, we prove the result.

The DLR procedure works more generally for weighted digraphs, and exposes an intriguing number-theoretic aspect of Woodall’s Conjecture. In fact, under natural number-theoretic conditions, Woodall’s Conjecture and a weighted extension of it are true. By pushing the barrier here, we expose strong base orderability as a key notion for tackling Woodall’s Conjecture.

Based on joint work with Gerard Cornuejols and Michael Zlatin.