Kevin Hendrey

activity

20152026

most citedBounds for the Twin-width of Graphs

15 citations · 73 across the 38 of their papers we have counts for

collaborators

Showing 2023Show all

5 papers · 1 filter

math.CO2023★ 2 cited

Twin-width of sparse random graphs

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

We show that the twin-width of every $n$ -vertex $d$ -regular graph is at most $n^{\frac{d - 2}{2 d - 2} + o (1)}$ and that almost all $d$ -regular graphs attain this bound. More generally, w…

math.CO2023

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…

math.CO2023

Finding dense minors using average degree

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$ -vertex minor in graphs of average degree at least $t - 1$ . We show that if $G$ has averag…

math.CO2023★ 4 cited

Twin-width of subdivisions of multigraphs

Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey +1

For each $d \leq 3$ , we construct a finite set $F_{d}$ of multigraphs such that for each graph $H$ of girth at least $5$ obtained from a multigraph $G$ by subdividing each edge at leas…

math.CO2023

Chromatic number is not tournament-local

António Girão, Kevin Hendrey, Freddie Illingworth +4

Scott and Seymour conjectured the existence of a function $f : N \to N$ such that, for every graph $G$ and tournament $T$ on the same vertex set, $χ(G) \geqs…