88 citations · 298 across the 33 of their papers we have counts for
39 papers
A relaxation of the Bermond-Thomassen conjecture
Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni +2
The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least contains vertex-disjoint directed cycles. Despite being posed in 198…
On the irreducibility and monodromy of Tutte polynomials
Andrew Goodall, Florent Jouve, Jean-Sébastien Sereni
We study algebraic properties of the Tutte polynomial of a matroid and its generalizations to other combinatorially defined bivariate polynomial invariants. Merino, de Mier and Noy…
An algorithmic framework for colouring locally sparse graphs
Ewan Davies, Ross J. Kang, François Pirot +1
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 fix…
Graph structure via local occupancy
Ewan Davies, Ross J. Kang, François Pirot +1
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 la…
Bipartite independence number in graphs with bounded maximum degree
Maria Axenovich, Jean-Sébastien Sereni, Richard Snyder +1
We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size in a bipartite graph is a copy of in the bipartite…
On the effect of symmetry requirement for rendezvous on the complete graph
Marthe Bonamy, Michał Pilipczuk, Jean-Sébastien Sereni
We consider a classic rendezvous game where two players try to meet each other on a set of locations. In each round, every player visits one of the locations and the game finis…
On fractional fragility rates of graph classes
Zdeněk Dvořák, Jean-Sébastien Sereni
We consider, for every positive integer , probability distributions on subsets of vertices of a graph with the property that every vertex belongs to the random set sampled from…
Revisiting a theorem by Folkman on graph colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain +5
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference…
Variations on the Petersen colouring conjecture
François Pirot, Jean-Sébastien Sereni, Riste Škrekovski
The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with colours such that for every edge , the set of colours assigned to th…
Fractional chromatic number, maximum degree and girth
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 vari…
Limits of Order Types
Xavier Goaoc, Alfredo Hubard, Rémi de Joannis de Verclos +2
We apply ideas from the theory of limits of dense combinatorial structures to study order types, which are combinatorial encodings of finite point sets. Using flag algebras we obta…
A -choosable graph that is not -choosable
Zdeněk Dvořák, Xiaolan Hu, Jean-Sébastien Sereni
In 1980, Erdős, Rubin and Taylor asked whether for all positive integers , , and , every -choosable graph is also -choosable. We provide a negative answer…
On generalized choice and coloring numbers
Zdeněk Dvořák, Jakub Pekárek, Jean-Sébastien Sereni
A well-known result of Alon shows that the coloring number of a graph is bounded by a function of its choosability. We explore this relationship in a more general setting with rela…
Equitable Colorings of -minor-free Graphs
Rémi De Joannis de Verclos, Jean-Sébastien Sereni
We demonstrate that for every positive integer , every K\_4-minor-free graph with maximum degree admits an equitable coloring with k colors wherek (+3)/2. This boun…
Do triangle-free planar graphs have exponentially many 3-colorings?
Zdeněk Dvořák, Jean-Sébastien Sereni
Thomassen conjectured that triangle-free planar graphs have an exponential number of -colorings. We show this conjecture to be equivalent to the following statement: there exist…
Closeness Centralization Measure for Two-mode Data of Prescribed Sizes
Matjaž Krnc, Jean-Sébastien Sereni, Riste Škrekovski +1
We confirm a conjecture by Everett, Sinclair, and Dankelmann~[Some Centrality results new and old, J. Math. Sociology 28 (2004), 215--227] regarding the problem of maximizing close…
Toward more localized local algorithms: removing assumptions concerning global knowledge
Amos Korman, Jean-Sébastien Sereni, Laurent Viennot
Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and -coloring algorithms by Barenboim…
Extension from Precoloured Sets of Edges
Katherine Edwards, António Girão, Jan van den Heuvel +3
We consider precolouring extension problems for proper edge-colourings of graphs and multigraphs, in an attempt to prove stronger versions of Vizing's and Shannon's bounds on the c…
Two floor building needing eight colors
Stéphane Bessy, Daniel Gonçalves, Jean-Sébastien Sereni
Motivated by frequency assignment in office blocks, we study the chromatic number of the adjacency graph of -dimensional parallelepiped arrangements. In the case each parallelep…
Isomorphism of Weighted Trees and Stanley's Conjecture for Caterpillars
Martin Loebl, Jean-Sébastien Sereni
This paper contributes to a programme initiated by the first author: `How much information about a graph is revealed in its Potts partition function?'. We show that the -polynom…
Fractional coloring of triangle-free planar graphs
Zdeněk Dvořák, Jean-Sébastien Sereni, Jan Volec
We prove that every planar triangle-free graph on vertices has fractional chromatic number at most .
A note on acyclic vertex-colorings
Jean-Sébastien Sereni, Jan Volec
We prove that the acyclic chromatic number of a graph with maximum degree is less than . This improves the previous upper bound, which was . To do so…
Supersaturation in the Boolean lattice
Andrew P. Dove, Jerrold R. Griggs, Ross J. Kang +1
We prove a "supersaturation-type" extension of both Sperner's Theorem (1928) and its generalization by Erdos (1945) to k-chains. Our result implies that a largest family whose size…
Transversals of Longest Paths and Cycles
Dieter Rautenbach, Jean-Sébastien Sereni
Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycl…