S. Bessy

activity

20082026

most citedBurning a Graph is Hard

6 citations · 24 across the 32 of their papers we have counts for

collaborators

Showing 2021 · math.COShow all

3 papers · 2 filters

math.CO2021

Factorially many maximum matchings close to the Erdős-Gallai bound

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta +1

A classical result of Erdős and Gallai determines the maximum size $m (n, ν)$ of a graph $G$ of order $n$ and matching number $ν n$ . We show that $G$ has factorially many maximum matc…

math.CO2021

Unbalanced spanning subgraphs in edge labeled complete graphs

Stéphane Bessy, Johannes Pardey, Lucas Picasarri-Arrieta +1

Let $K$ be a complete graph of order $n$ . For $d \in (0, 1)$ , let $c$ be a $\pm 1$ -edge labeling of $K$ such that there are $d (2 n)$ edges with label $+ 1$ , and let $G$ be a sp…

math.CO2021

Complementary cycles of any length in regular bipartite tournaments

Stéphane Bessy, Jocelyn Thiebaut

Let $D$ be a $k$ -regular bipartite tournament on $n$ vertices. We show that, for every $p$ with $2 \leq p \leq n /2 - 2$ , $D$ has a cycle $C$ of length $2 p$ such that $D ∖ C$ is…