6 papers
Multiparty equality in the local broadcast model
Louis Esperet, Jean-Florent Raymond
In this paper we consider the multiparty equality problem in graphs, where every vertex of a graph is given an input, and the goal of the vertices is to decide whether all inpu…
Local certification of geometric graph classes
Oscar Defrain, Louis Esperet, Aurélie Lagoutte +2
The goal of local certification is to locally convince the vertices of a graph that satisfies a given property. A prover assigns short certificates to the vertices of the g…
A quasi-optimal upper bound for induced paths in sparse graphs
Basile Couëtoux, Oscar Defrain, Jean-Florent Raymond
In 2012, NeÅ¡etÅil and Ossona de Mendez proved that graphs of bounded degeneracy that have a path of order also have an induced path of order . In this paper…
Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
Laurent Beaudou, Jan Bok, Florent Foucaud +2
The \emph{-neighbourhood complexity} of a graph is the function counting, for a given integer , the largest possible number, over all vertex-subsets of size , of s…
Long induced paths and forbidden patterns: Polylogarithmic bounds
Julien Duron, Louis Esperet, Jean-Florent Raymond
Consider a graph with a long path . When is it the case that also contains a long induced path? This question has been investigated in general as well as within a number…
Long induced paths in sparse graphs and graphs with forbidden patterns
Julien Duron, Louis Esperet, Jean-Florent Raymond
Consider a graph with a path of order . What conditions force to also have a long induced path? As complete bipartite graphs have long paths but no long induced path…