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 2021Show all

4 papers · 1 filter

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…

cs.DS2021

FPT algorithms for packing $k$ -safe spanning rooted sub(di)graphs

Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia +2

We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput. Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] about finding disjoint "balanced…

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…

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

Unbalanced spanning subgraphs in edge labeled complete graphs

FPT algorithms for packing k-safe spanning rooted sub(di)graphs

Complementary cycles of any length in regular bipartite tournaments

FPT algorithms for packing $k$ -safe spanning rooted sub(di)graphs