output
20082021
most citedOn a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture

22 citations

15 papers

cs.AI2021★ 4 cited

Planning with Biological Neurons and Synapses

Francesco d'Amore, Daniel Mitropolsky, Pierluigi Crescenzi +2

We revisit the planning problem in the blocks world, and we implement a known heuristic for this task. Importantly, our implementation is biologically plausible, in the sense that…

cs.DM2021

Hyperbolicity Computation through Dominating Sets

David Coudert, André Nusser, Laurent Viennot

Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning…

cs.DM2021

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…

cs.DM2021

A proof of the Multiplicative 1-2-3 Conjecture

Julien Bensmail, Hervé Hocquard, Dimitri Lajou +1

We prove that the product version of the 1-2-3 Conjecture, raised by Skowronek-Kazi{ó}w in 2012, is true. Namely, for every connected graph with order at least 3, we prove that we…

math.CO2021★ 5 cited

Modularity of minor-free graphs

Michał Lasoń, Małgorzata Sulkowska

We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, modularity tends to 1 as the numb…

cs.DC2020★ 5 cited

Phase Transition of a Non-Linear Opinion Dynamics with Noisy Interactions

Francesco d'Amore, Andrea Clementi, Emanuele Natale

In several real \emph{Multi-Agent Systems} (MAS), it has been observed that only weaker forms of\emph{metastable consensus} are achieved, in which a large majority of agents agree…

cs.DC2020★ 9 cited

Search via Parallel Lévy Walks on

Andrea Clementi, Francesco d'Amore, George Giakkoupis +1

Motivated by the Lévy foraging hypothesis -- the premise that various animal species have adapted to follow Lévy walks to optimize their search efficiency -- we study the parallel…

cs.CC2019

NP-completeness of the game Kingdomino

Viet-Ha Nguyen, Kevin Perrot, Mathieu Vallet

Kingdomino is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place dominoes on a grid layout, and get a better score than…

math.CO2017

Computing metric hulls in graphs

Kolja Knauer, Nicolas Nisse

We prove that, given a closure function the smallest preimage of a closed set can be calculated in polynomial time in the number of closed sets. This confirms a conjecture of Alben…

math.CO2017★ 22 cited

On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture

Julien Bensmail, Mohammed Senhaji, Kasper Szabo Lyngsie

This paper is dedicated to studying the following question: Is it always possible to injectively assign the weights to the edges of any given graph (with no comp…

math.CO2016★ 16 cited

A Variant of the Erdős-Sós Conjecture

Frédéric Havet, Bruce Reed, Maya Stein +1

A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding contains every tree with edges as a subgraph. We propose a variant of this…

cs.CC2016★ 3 cited

On computing tree and path decompositions with metric constraints on the bags

Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse

We here investigate on the complexity of computing the \emph{tree-length} and the \emph{tree-breadth} of any graph , that are respectively the best possible upper-bounds on the…

math.CO2016★ 18 cited

How to determine if a random graph with a fixed degree sequence has a giant component

Felix Joos, Guillem Perarnau, Dieter Rautenbach +1

For a fixed degree sequence , let be a uniformly chosen (simple) graph on where the vertex has degree . In this p…

math.CO2015★ 13 cited

Colouring graphs with constraints on connectivity

Pierre Aboulker, Nick Brettell, Frédéric Havet +2

A graph has maximal local edge-connectivity if the maximum number of edge-disjoint paths between every pair of distinct vertices and is at most . We prove Brooks…

math.CO2008★ 7 cited

List Colouring Squares of Planar Graphs

Frédéric Havet, Jan van den Heuvel, Colin McDiarmid +1

In 1977, Wegner conjectured that the chromatic number of the square of every planar graph with maximum degree is at most . We show t…