2 citations · 3 across the 10 of their papers we have counts for
12 papers
A Proof of the Linear Hadwiger Conjecture
Sergey Norin, Raphael Steiner
We show that there exists such that -minor free graphs are -colorable. The proof was found by GPT-6 Astra, following the directions by the authors.
Disproof of the dominating Hadwiger conjecture
Freddie Illingworth, Raphael Steiner
Hadwiger's conjecture (1943) states that every graph with chromatic number at least contains a -model: a collection of vertex-disjoint connected subgraphs $T_1,\do…
A relaxation of the Bermond-Thomassen conjecture
Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni +2
The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least contains vertex-disjoint directed cycles. Despite being posed in 198…
Disproof of the tree product conjecture via the Heisenberg group
Freddie Illingworth, Sergey Norin, Raphael Steiner
Product structure theory aims to understand complex graphs by embedding them into products of simpler graphs. In this direction, Campbell, Distel, Gollin, Harvey, Hendrey, Hickingb…
The Dominating 4-Colour Theorem
António Girão, Freddie Illingworth, Bojan Mohar +6
A "dominating -model" in a graph is a sequence of pairwise vertex-disjoint connected subgraphs of , such that whenever every vertex…
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…
Nowhere-zero flow reconfiguration
Louis Esperet, Kevin Hendrey, Aurélie Lagoutte +3
We initiate the study of nowhere-zero flow reconfiguration. The natural question is whether any two nowhere-zero -flows of a given graph are connected by a sequence of nowhe…
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…
Longest cycles in vertex-transitive and highly connected graphs
Carla Groenland, Sean Longbrake, Raphael Steiner +2
We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively,…
Optimal bounds for zero-sum cycles. I. Odd order
Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +1
For a finite (not necessarily Abelian) group , let denote the smallest positive integer such that for every labelling of the arcs of the comple…
Twin-width of sparse random graphs
Kevin Hendrey, Sergey Norin, Raphael Steiner +1
We show that the twin-width of every -vertex -regular graph is at most and that almost all -regular graphs attain this bound. More generally, w…
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…