15 papers
Optimal tree-decompositions with bags of bounded pathwidth
Kevin Hendrey, Robert Hickingbotham, JÄdrzej Hodor +1
The paper proves that every planar graph admits an optimal-width tree‑decomposition whose bags induce subgraphs of pathwidth at most three, and extends similar bounded‑pathwidth ba…
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 , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
The ErdÅs-Pósa property for prime-length cycles fails (and beyond)
Maximilian Gorsky, Kevin Hendrey, Tony Huynh
We prove that for every , prime-length cycles do not have the -integral ErdÅs-Pósa property, even when restricted to planar graphs. We in fact prov…
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…
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…
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…