6 papers
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…
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…
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 l…