13 citations · 36 across the 16 of their papers we have counts for
8 papers · 1 filter
Planar CPG graphs
Nicolas Champseix, Esther Galby, Bernard Ries
We show that for any , there exists a planar graph which is -CPG but not -CPG. As a consequence, we obtain that -CPG is a strict subclass of -…
Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width
Esther Galby, Andrea Munaro, Bernard Ries
A semitotal dominating set of a graph with no isolated vertex is a dominating set of such that every vertex in is within distance two of another vertex in . The…
Classifying k-Edge Colouring for H-free Graphs
Esther Galby, Paloma T. Lima, Daniel Paulusma +1
A graph is -free if it does not contain an induced subgraph isomorphic to . For every integer and every graph , we determine the computational complexity of -Edge C…
Maximum Eccentric Connectivity Index for Graphs with Given Diameter
Pierre Hauweele, Alain Hertz, Hadrien Mélot +2
The eccentricity of a vertex in a graph is the maximum distance between and any other vertex of . The diameter of a graph is the maximum eccentricity of a vertex…
Proper circular arc graphs as intersection graphs of paths on a grid
Esther Galby, Maria Pia Mazzoleni, Bernard Ries
In this paper we present a characterisation, by an infinite family of minimal forbidden induced subgraphs, of proper circular arc graphs which are intersection graphs of paths on a…
Detecting strong cliques
Ademir Hujdurović, Martin Milanič, Bernard Ries
A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliq…