Showing cs.DMShow all
3 papers · 1 filter
cs.DM2025
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…
cs.DM2024
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…
cs.DM2023
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…