6 papers · 1 filter
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…
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…
Defective coloring of blowups
Sergey Norin, Raphael Steiner
Given a graph and an integer , its -defective chromatic number is the smallest size of a partition of the vertices into parts inducing subgraphs with maximu…
Strong parity edge-colorings of graphs
Peter Bradshaw, Sergey Norin, Douglas B. West
An edge-coloring of a graph assigns a color to each edge of . An edge-coloring is a parity edge-coloring if for each path in , it uses some color on an odd number of…
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…