Showing 2025 · math.COShow all
3 papers · 2 filters
math.CO2025
Small hitting sets for longest paths and cycles
Sergey Norin, Raphael Steiner, Stephan Thomassé +1
Motivated by an old question of Gallai (1966) on the intersection of longest paths in a graph and the well-known conjectures of Lovász (1969) and Thomassen (1978) on the maximum le…
math.CO2025
Two-block paths in oriented graphs of large semidegree
Irena Penev, S Taruni, Stéphan Thomassé +2
We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive i…
math.CO2025
Lollipops, dense cycles and chords
Zdeněk Dvořák, Beatriz Martins, Stéphan Thomassé +1
In 1980, Gupta, Kahn and Robertson proved that every graph with minimum degree at least contains a cycle containing at least vertices each having at least $…