12 citations · 49 across the 20 of their papers we have counts for
6 papers · 1 filter
Splitting vertices of bipartite graphs preserves de Bruijn-Erdős property
Laurent Beaudou, Guillermo Gamboa Quintero
In this note, we prove that every graph obtained from a bipartite graph by iteratively splitting vertices into two adjacent twins has the de Bruijn-Erdős property.
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…
Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly
Laurent Beaudou, Caroline Brosse, Oscar Defrain +4
The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $σ= v_1,\dots,v_…
Graphs with no induced house nor induced hole have the de Bruijn-Erdős property
Pierre Aboulker, Laurent Beaudou, Martín Matamala +1
A set of n points in the plane which are not all collinear defines at least n distinct lines. Chen and Chvátal conjectured in 2008 that a similar result can be achieved in the broa…
Bisplit graphs satisfy the Chen-Chvátal conjecture
Laurent Beaudou, Giacomo Kahn, Matthieu Rosenfeld
In this paper, we give a lengthy proof of a small result! A graph is bisplit if its vertex set can be partitioned into three stable sets with two of them inducing a complete bipart…
On the multipacking number of grid graphs
Laurent Beaudou, Richard C. Brewster
In 2001, Erwin introduced broadcast domination in graphs. It is a variant of classical domination where selected vertices may have different domination powers. The minimum cost of…