291 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre National de la Recherche ScientifiqueFR223 papers
- Université de MontpellierFR184 papers
- Institut national de recherche en sciences et technologies du numériqueFR39 papers
- Université Montpellier 233 papers
- Data Management (Italy)IT24 papers
- Institut National Polytechnique de ToulouseFR24 papers
- Université Paul-Valéry MontpellierFR17 papers
- École Normale Supérieure de LyonFR16 papers
- Centre de Coopération Internationale en Recherche Agronomique pour le DéveloppementFR15 papers
- National and Kapodistrian University of AthensGR15 papers
- Lyon 1 UniversitéFR11 papers
- UMR Botanique et Modélisation de l’Architecture des Plantes et des végétationsFR11 papers
9 papers · 2 filters
Brooks' theorem on powers of graphs
Marthe Bonamy, Nicolas Bousquet
We prove that for , the bound given by Brooks' theorem on the chromatic number of -th powers of graphs of maximum degree can be lowered by 1, even in the case…
Computation with No Memory, and Rearrangeable Multicast Networks
Serge Burckel, Emeric Gioan, Emmanuel Thomé
We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one co…
-Limit Sets of Cellular Automata from a Computational Complexity Perspective
Laurent Boyer, Martin Delacourt, Victor Poupet +2
This paper concerns -limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial -ra…
List coloring the square of sparse graphs with large degree
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou
We consider the problem of coloring the squares of graphs of bounded maximum average degree, that is, the problem of coloring the vertices while ensuring that two vertices that are…
Polynomial Gap Extensions of the Erdős-Pósa Theorem
Jean-Florent Raymond, Dimitrios M. Thilikos
Given a graph , we denote by all graphs that can be contracted to . The following extension of the Erdős-Pósa Theorem holds: for every -vertex planar graph $…
Probabilistic Constructions of Computable Objects and a Computable Version of Lovász Local Lemma
Andrei Rumyantsev, Alexander Shen
A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such an object. A special case is a probabilis…
On Quasiperiodic Morphisms
Florence Levé, Gwénaël Richomme
Weakly and strongly quasiperiodic morphisms are tools introduced to study quasiperiodic words. Formally they map respectively at least one or any non-quasiperiodic word to a quasip…
Recoloring bounded treewidth graphs
Marthe Bonamy, Nicolas Bousquet
Let be an integer. Two vertex -colorings of a graph are \emph{adjacent} if they differ on exactly one vertex. A graph is \emph{-mixing} if any proper -coloring can be…
Clique versus Independent Set
Nicolas Bousquet, Aurélie Lagoutte, Stéphan Thomassé
Yannakakis' Clique versus Independent Set problem (CL-IS) in communication complexity asks for the minimum number of cuts separating cliques from stable sets in a graph, called CS-…