Source author record

Bastien Durain

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

2works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Extremal Independent Set Reconfiguration

The independent set reconfiguration problem asks whether one can transform one given independent set of a graph into another, by changing vertices one by one in such a way the intermediate sets remain independent. Extremal problems on independent sets are widely studied: for example, it is well known that an $n$ -vertex graph has at most $3^{n/3}$ maximum independent sets (and this is tight). This paper investigates the asymptotic behavior of maximum possible length of a shortest reconfiguration sequence for independent sets of size $k$ among all $n$ -vertex graphs. We give a tight bound for $k=2$ . We also provide a subquadratic upper bound (using the hypergraph removal lemma) as well as an almost tight construction for $k=3$ . We generalize our results for larger values of $k$ by proving an $n^{2\lfloor k/3 \rfloor}$ lower bound.

preprint2020arXiv

A note on the simultaneous edge coloring

Let $G=(V,E)$ be a graph. A (proper) $k$ -edge-coloring is a coloring of the edges of $G$ such that any pair of edges sharing an endpoint receive distinct colors. A classical result of Vizing ensures that any simple graph $G$ admits a $(Δ(G)+1)$ -edge coloring where $Δ(G)$ denotes the maximum degreee of $G$ . Recently, Cabello raised the following question: given two graphs $G_1,G_2$ of maximum degree $Δ$ on the same set of vertices $V$ , is it possible to edge-color their (edge) union with $Δ+2$ colors in such a way the restriction of $G$ to respectively the edges of $G_1$ and the edges of $G_2$ are edge-colorings? More generally, given $\ell$ graphs, how many colors do we need to color their union in such a way the restriction of the coloring to each graph is proper? In this short note, we prove that we can always color the union of the graphs $G_1,\ldots,G_\ell$ of maximum degree $Δ$ with $Ω(\sqrt{\ell} \cdot Δ)$ colors and that there exist graphs for which this bound is tight up to a constant multiplicative factor. Moreover, for two graphs, we prove that at most $\frac 32 Δ+4$ colors are enough which is, as far as we know, the best known upper bound.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.