JSJean-Sébastien Sereni

Jean-Sébastien Sereni

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Jean-Sébastien Sereni has a total of 68 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Trinucleotide k-circular codes II: Biology

    by Christian J. Michel, Jean-Sébastien Sereni


  • Trinucleotide k-circular codes I: Theory

    by Christian J. Michel, Baptiste Mouillon, Jean-Sébastien Sereni


    • 9 December 2021
    • Published by HAL in HAL
    Open Access

    The minimum number of spanning trees in regular multigraphs I: the odd-degree case

    by Jakub Pekárek, Jean-Sébastien Sereni, Zelealem B Yilma

    This pre-publication was merged with "The minimum number of spanning trees in regular multigraphs II: the even-degree case" (hal-03472283).The resulting full article has been published in The Electronic Journal of Combinatorics (https://doi.org/10.37236/10911) and is also availableon HAL (hal-03860510).Cette prépublication a été fusionnée avec "The minimum number of spanning trees in regular multigraphs II: the even-degree case" (hal-03472283), donnant lieu à un article publié dans The Electronic Journal of Combinatorics (https://doi.org/10.37236/10911) et disponibleaussi sur HAL (hal-03860510).

  • Open Access

    Fractional chromatic number, maximum degree and girth

    by François Pirot, Jean-Sébastien Sereni

    We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints, and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree~$\Delta \ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of~$\Delta$, and improves it when~$\Delta\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of~$\Delta$, we also demonstrate that every graph of girth at least~$7$ and maximum degree~$\Delta$ has fractional chromatic number at most~$1+ \min_{k \in \mathbb{N}} \frac{2\Delta + 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth~$7$ and maximum degree~$\Delta$ is at most~$\frac{2\Delta+9}{5}$ when~$\Delta \in [3,8]$, at most~$\frac{\Delta+7}{3}$ when~$\Delta \in [8,20]$, at most~$\frac{2\Delta+23}{7}$ when~$\Delta \in [20,48]$, and at most~$\frac{\Delta}{4}+5$ when~$\Delta \in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree~$\Delta \in \{3,4,5\}$ and girth~$g\in \{6,\dotsc,12\}$, notably~$1/3$ when~$(\Delta,g)=(4,10)$ and~$2/7$ when~$(\Delta,g)=(5,8)$.

  • Open Access

    On Fractional Fragility Rates of Graph Classes

    by Zdeněk Dvořák, Jean-Sébastien Sereni

    We consider, for every positive integer $a$, probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from this distribution with probability at most $1/a$. Among other results, we prove that for every positive integer $a$ and every planar graph $G$, there exists such a probability distribution with the additional property that for any set $X$ in the support of the distribution, the graph $G-X$ has component-size at most $(\Delta(G)-1)^{a+O(\sqrt{a})}$, or treedepth at most $O(a^3\log_2(a))$. We also provide nearly-matching lower bounds.


  • The Relation Between k-Circularity and Circularity of Codes

    by Elena Fimmel, Christian J. Michel, François Pirot, Jean-Sébastien Sereni, Martin Starman, Lutz Strüngmann

    A code X is k-circular if any concatenation of at most k words from X, when read on a circle, admits exactly one partition into words from X. It is circular if it is k-circular for every integer k. While it is not a priori clear from the definition, there exists, for every pair \((n,\ell )\), an integer k such that every k-circular \(\ell \)-letter code over an alphabet of cardinality n is circular, and we determine the least such integer k for all values of n and \(\ell \). The k-circular codes may represent an important evolutionary step between the circular codes, such as the comma-free codes, and the genetic code.


  • Open Access

    An algorithmic framework for colouring locally sparse graphs

    by Ewan Davies, Ross J. Kang, François Pirot, Jean-Sébastien Sereni

    We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $\Delta$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2\le t\le \Delta^\frac{2\varepsilon}{1+2\varepsilon}/(\log\Delta)^2$, with $\lfloor(1+\varepsilon)\Delta/\log(\Delta/\sqrt t)\rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs.

  • Open Access

    Graph structure via local occupancy

    by Ewan Davies, Ross J. Kang, François Pirot, Jean-Sébastien Sereni

    The first author together with Jenssen, Perkins and Roberts (2017) recently showed how local properties of the hard-core model on triangle-free graphs guarantee the existence of large independent sets, of size matching the best-known asymptotics due to Shearer (1983). The present work strengthens this in two ways: first, by guaranteeing stronger graph structure in terms of colourings through applications of the Lov\'asz local lemma; and second, by extending beyond triangle-free graphs in terms of local sparsity, treating for example graphs of bounded local edge density, of bounded local Hall ratio, and of bounded clique number. This generalises and improves upon much other earlier work, including that of Shearer (1995), Alon (1996) and Alon, Krivelevich and Sudakov (1999), and more recent results of Molloy (2019), Bernshteyn (2019) and Achlioptas, Iliopoulos and Sinclair (2019). Our results derive from a common framework built around the hard-core model. It pivots on a property we call local occupancy, giving a clean separation between the methods for deriving graph structure with probabilistic information and verifying the requisite probabilistic information itself.

  • Open Access

    Revisiting a theorem by Folkman on graph colouring

    by Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwenaël Joret, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor, Jean-Sébastien Sereni

    We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most $2$ plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number.

    • 25 February 2020
    • Published by HAL in HAL
    Open Access

    Bipartite independence number in graphs with bounded maximum degree

    by Maria Axenovich, Jean-Sébastien Sereni, Richard Snyder, Lea Weber

    Come from teaching and research institutions in France or abroad, or from public or private research centers. L'archive ouverte pluridisciplinaire