Showing 2026Show all
3 papers · 1 filter
math.CO2026
Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
Romain Bourneuf, Raphael Steiner, Stéphan Thomassé +1
We determine the asymmetric homomorphism threshold from graphs of odd girth at least to triangle-free graphs, showing that .…
math.CO2026
Proof of Lichiardopol's conjecture on disjoint directed cycles of distinct lengths
Sandra Albrechtsen, Raphael Steiner
There is a fascinating array of interrelated questions studying which structures can be guaranteed in digraphs of large minimum out-degree. These often have intriguingly simple sta…
math.CO2026
Towards the Lovász conjecture via sublinear expanders
Matija Bucić, Micha Christoph, Alexey Pokrovskiy +1
Lovász' famous Hamiltonicity conjecture (1969) states that every connected vertex-transitive graph has a Hamiltonian path. A stronger version of the conjecture, often attributed to…