Tag: KevinHendrey

The strong product $G\boxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)\times V(H)$ such that vertices $(v,w)$ and $(x,y)$ are adjacent if and only if $\max\{d_G(v,x),d_H(w,y)\}=1$. Graph product structure theory aims to describe complicated graphs in terms of subgraphs of strong products of simpler graphs. This area of research was initiated by Dujmović, Joret, Micek, Morin, Ueckerdt and Wood, who showed that every planar graph is a subgraph of the strong product of a $H\boxtimes P\boxtimes K_3$ for some path $P$ and some graph $H$ of treewidth at most $3$. In this talk, I will discuss the product structure of various graph classes of bounded treewidth. As an example, we show that there is a function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that every planar graph of treewidth at most $k$ is a subgraph of $H\boxtimes K_{f(k)}$ for some graph $H$ of treewidth at most $3$.

This is based on joint work with Campbell, Clinch, Distel, Gollin, Hickingbotham, Huynh, Illingworth, Tamitegama, Tan and Wood.

This talk follows on from the recent talk of Pascal Gollin in this seminar series, but will aim to be accessible for newcomers.

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By relaxing `packing’ to `half-integral packing’, Reed obtained an analogous result for odd cycles, and gave a structural characterisation of when the (integral) packing version fails.

We prove some far-reaching generalisations of these theorems. First, we show that if the edges of a graph are labelled by finitely many abelian groups, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property. Similarly to Reed, we give a structural characterisation for the failure of the integral Erdős-Pósa property in this setting. This allows us to deduce the full Erdős-Pósa property for many natural classes of cycles.

We will look at applications of these results to graphs embedded on surfaces, and also discuss some possibilities and obstacles for extending these results.

This is joint work with Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-il Oum, and Youngho Yoo.

The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$, as well as almost all graphs of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph $H$, \[c(H) = (1+o(1))\max (v(H)/2, v(H)-\alpha(H)),\] extending recent results of Haslegrave, Kim and Liu (2020). Joint work with Sergey Norin and David R. Wood.

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles.  However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles.

A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least $\ell$, cycles of length $p$ modulo $q$, cycles intersecting a prescribed set of vertices at least $t$ times, and cycles contained in given $\mathbb{Z}_2$-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.

This is joint work with J. Pascal Gollin, Ken-ichi Kawarabayashi, O-joung Kwon, and Sang-il Oum.