Kevin Hendrey

activity

20152026

most citedBounds for the Twin-width of Graphs

15 citations · 73 across the 38 of their papers we have counts for

collaborators

41 papers

math.GR2026

Complete Mappings of Semigroups

João Araújo, Wolfram Bentz, Peter J. Cameron +2

A complete mapping of a semigroup $S$ is a bijection $α : S \to S$ such that the map $θ : S \to S$ defined by $x θ = x \cdot xα$ is also a bijection. Equivalently, it determines…

math.CO2026

Optimal tree-decompositions with bags of bounded pathwidth

Kevin Hendrey, Robert Hickingbotham, Jędrzej Hodor +1

We show that every planar graph has a tree-decomposition with optimal width such that the subgraph induced by each bag has pathwidth at most 3. This bound is best possible, and for…

math.CO2026

An Erdős-Pósa theorem for cycles and faces of distinct lengths

J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6

We show that for every $k \in N$ , every graph $G$ contains $k$ vertex-disjoint cycles of different lengths, or there exists a set $X \subseteq V (G)$ with $|X| \in \mathcal…

math.CO2026

The Erdős-Pósa property for prime-length cycles fails (and beyond)

Maximilian Gorsky, Kevin Hendrey, Tony Huynh

We prove that for every $t \in N$ , prime-length cycles do not have the $\frac{1}{t}$ -integral Erdős-Pósa property, even when restricted to planar graphs. We in fact prove…

math.CO2026

Long cycles in vertex transitive digraphs

Matija Bucić, Kevin Hendrey, Bojan Mohar +2

One of the most well-known conjectures concerning Hamiltonicity in graphs asserts that any sufficiently large connected vertex transitive graph contains a Hamilton cycle. In this f…

math.CO2025

Blind cop-width and balanced minors of graphs

Hector Buffière, Rutger Campbell, Kevin Hendrey +1

We investigate a pursuit-evasion game on an undirected graph in which a robber, moving at a fixed constant speed, attempts to evade a team of cops who are blind to the robber's loc…

math.CO2025

Optimal Tree-Decompositions with Bags of Bounded Treewidth

Kevin Hendrey, David R. Wood

We prove that several natural graph classes have tree-decompositions with minimum width such that each bag has bounded treewidth. For example, every planar graph has a tree-decompo…

math.CO2025

Embedding Graphs of Simple Treewidth into Sparse Products

Kevin Hendrey, David R. Wood, Jung Hon Yip

We study embeddings of graphs with bounded treewidth or bounded simple treewidth into the undirected graph underlying the directed product of two directed graphs. If the factors ha…

math.CO2025

Unavoidable pivot-minors in graphs of large rank-depth

Jungho Ahn, Kevin Hendrey, O-joung Kwon +1

Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer $t$ , every graph of sufficiently large rank-d…

math.CO2025

Structure of $k$ -Matching-Planar Graphs

Kevin Hendrey, Nikolai Karol, David R. Wood

For $k ⩾ 0$ , we define a simple topological graph $G$ (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be…

math.CO2025

Polynomial Bounds in the Apex Minor Theorem

Kevin Hendrey, David R. Wood

A graph $A$ is "apex" if $A - z$ is planar for some vertex $z \in V (A)$ . Eppstein [Algorithmica, 2000] showed that for a minor-closed class $G$ , the graphs in $G$ …

math.CO2025

Short Paths in the Planar Graph Product Structure Theorem

Kevin Hendrey, David R. Wood

The Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM '20] says that every planar graph $G$ is contained in $H ⊠ P ⊠ K_{3}$ for some planar graph $H$ wi…

math.CO2025

Metric graphs of negative type

Rutger Campbell, Kevin Hendrey, Ben Lund +1

The negative type inequalities of a metric space are closely tied to embeddability. A result by Gupta, Newman, and Rabinovich implies that if a metric graph $G$ does not contain a…

math.CO2024

Treewidth 2 in the Planar Graph Product Structure Theorem

Marc Distel, Kevin Hendrey, Nikolai Karol +2

We prove that every planar graph is contained in $H_{1} ⊠ H_{2} ⊠ K_{2}$ for some graphs $H_{1}$ and $H_{2}$ both with treewidth 2. This resolves a question of Liu, Norin and W…

math.CO2024

Treewidth, Hadwiger Number, and Induced Minors

Rutger Campbell, James Davies, Marc Distel +7

Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence o…

math.CO2024

Clustered Colouring of Graph Products

Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +5

A colouring of a graph $G$ has clustering $k$ if the maximum number of vertices in a monochromatic component equals $k$ . Motivated by recent results showing that many natural graph…

math.CO2024

Optimal bounds for zero-sum cycles. I. Odd order

Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +1

For a finite (not necessarily Abelian) group $(Γ, \cdot)$ , let $n (Γ) \in N$ denote the smallest positive integer $n$ such that for every labelling of the arcs of the comple…

math.CO2024

When $t$ -intersecting hypergraphs admit bounded $c$ -strong colourings

Kevin Hendrey, Freddie Illingworth, Nina Kamčev +1

The $c$ -strong chromatic number of a hypergraph is the smallest number of colours needed to colour its vertices so that every edge sees at least $c$ colours or is rainbow. We show…

math.CO2024

Sharing tea on a graph

J. Pascal Gollin, Kevin Hendrey, Hao Huang +6

Motivated by the analysis of consensus formation in the Deffuant model for social interaction, we consider the following procedure on a graph $G$ . Initially, there is one unit of t…

math.CO2024

Linear bounds on treewidth in terms of excluded planar minors

J. Pascal Gollin, Kevin Hendrey, Sang-il Oum +1

One of the fundamental results in graph minor theory is that for every planar graph $H$ , there is a minimum integer $f (H)$ such that graphs with no minor isomorphic to $H$ have tre…

math.CO2023★ 2 cited

Twin-width of sparse random graphs

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

We show that the twin-width of every $n$ -vertex $d$ -regular graph is at most $n^{\frac{d - 2}{2 d - 2} + o (1)}$ and that almost all $d$ -regular graphs attain this bound. More generally, w…

math.CO2023

On an induced version of Menger's theorem

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

We prove Menger-type results in which the obtained paths are pairwise non-adjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topologica…

math.CO2023

Finding dense minors using average degree

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$ -vertex minor in graphs of average degree at least $t - 1$ . We show that if $G$ has averag…

math.CO2023★ 4 cited

Twin-width of subdivisions of multigraphs

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +1

For each $d \leq 3$ , we construct a finite set $F_{d}$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at leas…

Complete Mappings of Semigroups

Optimal tree-decompositions with bags of bounded pathwidth

An Erdős-Pósa theorem for cycles and faces of distinct lengths

The Erdős-Pósa property for prime-length cycles fails (and beyond)

Long cycles in vertex transitive digraphs

Blind cop-width and balanced minors of graphs

Optimal Tree-Decompositions with Bags of Bounded Treewidth

Embedding Graphs of Simple Treewidth into Sparse Products

Unavoidable pivot-minors in graphs of large rank-depth

Structure of k-Matching-Planar Graphs

Polynomial Bounds in the Apex Minor Theorem

Short Paths in the Planar Graph Product Structure Theorem

Metric graphs of negative type

Treewidth 2 in the Planar Graph Product Structure Theorem

Treewidth, Hadwiger Number, and Induced Minors

Clustered Colouring of Graph Products

Optimal bounds for zero-sum cycles. I. Odd order

When t-intersecting hypergraphs admit bounded c-strong colourings

Sharing tea on a graph

Linear bounds on treewidth in terms of excluded planar minors

Twin-width of sparse random graphs

On an induced version of Menger's theorem

Finding dense minors using average degree

Twin-width of subdivisions of multigraphs

Structure of $k$ -Matching-Planar Graphs

When $t$ -intersecting hypergraphs admit bounded $c$ -strong colourings