471 citations
- Lyon 1 UniversitéFR95 papers
- Centre National de la Recherche ScientifiqueFR92 papers
- Institut National des Sciences Appliquées de LyonFR59 papers
- École Centrale de LyonFR19 papers
- Institut national de recherche en sciences et technologies du numériqueFR18 papers
- Université de LyonFR16 papers
- Université Grenoble AlpesFR12 papers
- École Normale Supérieure de LyonFR10 papers
- LabEx PERSYVAL-LabFR10 papers
- Laboratoire d'Informatique, de Modélisation et d'Optimisation des SystèmesFR10 papers
- Universidade Federal de PernambucoBR8 papers
- Commissariat à l'Énergie Atomique et aux Énergies AlternativesFR7 papers
8 papers · 1 filter
Fast winning strategies for the attacker in eternal domination
Guillaume Bagan, Nicolas Bousquet, Nacim Oijid +1
Dominating sets in graphs are often used to model some monitoring of the graph: guards are posted on the vertices of the dominating set, and they can thus react to attacks occurrin…
Digraph redicolouring
Nicolas Bousquet, Frédéric Havet, Nicolas Nisse +2
Given two -dicolourings of a digraph , we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while…
Hypergraphs with Polynomial Representation: Introducing -splits
François Pitois, Mohammed Haddad, Hamida Seba +1
Inspired by the split decomposition of graphs and rank-width, we introduce the notion of -splits. We focus on the family of -splits of a graph of order , and we prove that…
Generalising the achromatic number to Zaslavsky's colourings of signed graphs
Julien Bensmail, François Dross, Nacim Oijid +1
The chromatic number, which refers to the minimum number of colours required to colour the vertices of graphs properly, is one of the most central notions of the graph chromatic th…
A Vizing-like theorem for union vertex-distinguishing edge coloring
Nicolas Bousquet, Antoine Dailly, Eric Duchene +2
We introduce a variant of the vertex-distinguishing edge coloring problem, where each edge is assigned a subset of colors. The label of a vertex is the union of the sets of colors…
Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
Florent Foucaud, George B. Mertzios, Reza Naserasr +2
We consider the problems of finding optimal identifying codes, (open) locating-dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks…