Kevin Hendrey
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Kevin Hendrey has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Sang-Il Oum
Discrete Mathematics Group Institute for Basic Science (IBS) Daejeon South Korea
3 shared publications - David R. Wood
Monash University, Melbourne, Australia
2 shared publications - Jochen Pascal Gollin
FAMNIT, University of Primorska, Koper, Slovenia
2 shared publications - O-Joung Kwon
Department of Mathematics, Hanyang University, Seoul, South Korea
2 shared publications - Bryce Frederickson
Department of Mathematics Emory University Atlanta GA
1 shared publication - Hector Buffière
IRIF Université Paris Cité Paris France
1 shared publication
Latest Publications
- Open Access
Blind cop-width and balanced minors of graphs
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 location and can quickly travel between any pair of vertices in the graph. The blind cop-width is the minimum number of cops needed to catch the robber on a given graph. We link it with other known graph parameters defined in terms of pursuit-evasion games, and show a new lower bound with respect to treewidth. The proof introduces the notion of balanced minors, where all branch sets of a minor model have equal size.
Open AccessBlind cop-width and balanced minors of graphs
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 location and can quickly travel between any pair of vertices in the graph. The blind cop-width is the minimum number of cops needed to catch the robber on a given graph. We link it with other known graph parameters defined in terms of pursuit-evasion games, and show a new lower bound with respect to treewidth. The proof introduces the notion of balanced minors, where all branch sets of a minor model have equal size.
- Open Access
- 26 September 2025
- Published by Springer Nature in Mathematische Annalen
- Vol. 393 (2) , 2507-2559
A unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
In 1965, Erdős and Pósa proved that there is an (approximate) 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 for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs $${(\ell , z)}$$ of integers where such a duality holds for the family of cycles of length $$\ell $$ modulo z . We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface.- 26 September 2025
- Published by Springer Nature in Mathematische Annalen
- Vol. 393 (2) , 2507-2559
Open AccessA unified Erdős–Pósa theorem for cycles in graphs labelled by multiple abelian groups
In 1965, Erdős and Pósa proved that there is an (approximate) 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 for odd cycles, and Dejter and Neumann-Lara asked in 1988 to find all pairs $${(\ell , z)}$$ of integers where such a duality holds for the family of cycles of length $$\ell $$ modulo z . We characterise all such pairs, and we further generalise this characterisation to cycles in graphs labelled with a bounded number of abelian groups, whose values avoid a bounded number of elements of each group. This unifies almost all known types of cycles that admit such a duality, and it also provides new results. Moreover, we characterise the obstructions to such a duality in this setting, and thereby obtain an analogous characterisation for cycles in graphs embeddable on a fixed compact orientable surface. - Open Access
Unavoidable pivot-minors in graphs of large rank-depth
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-depth contains a pivot-minor isomorphic to a path on $t$ vertices or a graph consisting of two disjoint cliques of size $t$ joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021.Open AccessUnavoidable pivot-minors in graphs of large rank-depth
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-depth contains a pivot-minor isomorphic to a path on $t$ vertices or a graph consisting of two disjoint cliques of size $t$ joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021. - Open Access
Short Paths in the Planar Graph Product Structure Theorem
The Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM '20] says that every planar graph $G$ is contained in $H\boxtimes P\boxtimes K_3$ for some planar graph $H$ with treewidth at most 3 and some path $P$. This result has been the key to solving several old open problems. Several people have asked whether the Planar Graph Product Structure Theorem can be proved with good upper bounds on the length of $P$. No $o(n)$ upper bound was previously known for $n$-vertex planar graphs. We answer this question in the affirmative, by proving that for any $ε\in (0,1)$ every $n$-vertex planar graph is contained in $H\boxtimes P\boxtimes K_{O(1/ε)}$, for some planar graph $H$ with treewidth 3 and for some path $P$ of length $O(\frac{1}εn^{(1+ε)/2})$. This bound is almost tight since there is a lower bound of $Ω(n^{1/2})$ for certain $n$-vertex planar graphs. In fact, we prove a stronger result with $P$ of length $O(\frac{1}ε\,\textrm{tw}(G)\,n^ε)$, which is tight up to the $O(\frac{1}ε\,n^ε)$ factor for every $n$-vertex planar graph $G$. Finally, taking $ε=\frac{1}{\log n}$, we show that every $n$-vertex planar graph $G$ is contained in $H\boxtimes P\boxtimes K_{O(\log n)}$ for some planar graph $H$ with treewidth at most 3 and some path $P$ of length $O(\textrm{tw}(G)\,\log n)$. This result is particularly attractive since the treewidth of the product $H\boxtimes P\boxtimes K_{O(\log n)}$ is within a $O(\log^2n)$ factor of the treewidth of $G$.Open AccessShort Paths in the Planar Graph Product Structure Theorem
The Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM '20] says that every planar graph $G$ is contained in $H\boxtimes P\boxtimes K_3$ for some planar graph $H$ with treewidth at most 3 and some path $P$. This result has been the key to solving several old open problems. Several people have asked whether the Planar Graph Product Structure Theorem can be proved with good upper bounds on the length of $P$. No $o(n)$ upper bound was previously known for $n$-vertex planar graphs. We answer this question in the affirmative, by proving that for any $ε\in (0,1)$ every $n$-vertex planar graph is contained in $H\boxtimes P\boxtimes K_{O(1/ε)}$, for some planar graph $H$ with treewidth 3 and for some path $P$ of length $O(\frac{1}εn^{(1+ε)/2})$. This bound is almost tight since there is a lower bound of $Ω(n^{1/2})$ for certain $n$-vertex planar graphs. In fact, we prove a stronger result with $P$ of length $O(\frac{1}ε\,\textrm{tw}(G)\,n^ε)$, which is tight up to the $O(\frac{1}ε\,n^ε)$ factor for every $n$-vertex planar graph $G$. Finally, taking $ε=\frac{1}{\log n}$, we show that every $n$-vertex planar graph $G$ is contained in $H\boxtimes P\boxtimes K_{O(\log n)}$ for some planar graph $H$ with treewidth at most 3 and some path $P$ of length $O(\textrm{tw}(G)\,\log n)$. This result is particularly attractive since the treewidth of the product $H\boxtimes P\boxtimes K_{O(\log n)}$ is within a $O(\log^2n)$ factor of the treewidth of $G$. - Open Access
Treewidth, Hadwiger Number, and Induced Minors
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 of a large complete graph minor. To formalise this, we say that a graph class $\mathcal{G}$ is (tw,had)-bounded if there is a function $f$ (called the (tw,had)-bounding function) such that tw$(G)$ $\leq$ $f$(had$(G)$) for every graph $G \in \mathcal{G}$. We characterise (tw,had)-bounded graph classes as those that exclude some planar graph as an induced minor, and use this characterisation to show that every proper vertex-minor-closed class is (tw,had)-bounded. Furthermore, we demonstrate that any (tw,had)-bounded graph class has a (tw,had)-bounding function in O(had$(G)^9$polylog(had$(G)$)). Our bound comes from the bound for the Grid Minor Theorem given by Chuzhoy and Tan, and any quantitative improvement to their result will lead directly to an improvement to our result. More strongly, we conjecture that every (tw,had)-bounded graph class has a linear (tw,had)-bounding function. In support of this conjecture, we show that it holds for the class of outer-string graphs, and for a natural generalisation of outer-string graphs: intersection graphs of strings rooted at the boundary of a fixed surface. We also verify our conjecture for low-rank perturbations of circle graphs, which is an important step towards verifying it for all proper vertex-minor-closed classes.Open AccessTreewidth, Hadwiger Number, and Induced Minors
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 of a large complete graph minor. To formalise this, we say that a graph class $\mathcal{G}$ is (tw,had)-bounded if there is a function $f$ (called the (tw,had)-bounding function) such that tw$(G)$ $\leq$ $f$(had$(G)$) for every graph $G \in \mathcal{G}$. We characterise (tw,had)-bounded graph classes as those that exclude some planar graph as an induced minor, and use this characterisation to show that every proper vertex-minor-closed class is (tw,had)-bounded. Furthermore, we demonstrate that any (tw,had)-bounded graph class has a (tw,had)-bounding function in O(had$(G)^9$polylog(had$(G)$)). Our bound comes from the bound for the Grid Minor Theorem given by Chuzhoy and Tan, and any quantitative improvement to their result will lead directly to an improvement to our result. More strongly, we conjecture that every (tw,had)-bounded graph class has a linear (tw,had)-bounding function. In support of this conjecture, we show that it holds for the class of outer-string graphs, and for a natural generalisation of outer-string graphs: intersection graphs of strings rooted at the boundary of a fixed surface. We also verify our conjecture for low-rank perturbations of circle graphs, which is an important step towards verifying it for all proper vertex-minor-closed classes.