22 citations · 112 across the 37 of their papers we have counts for
4 papers · 1 filter
Locally identifying colourings for graphs with given maximum degree
Florent Foucaud, Iiro Honkala, Tero Laihonen +2
A proper vertex-colouring of a graph G is said to be locally identifying if for any pair u,v of adjacent vertices with distinct closed neighbourhoods, the sets of colours in the cl…
Rainbow Matchings: existence and counting
Guillem Perarnau, Oriol Serra
A perfect matching M in an edge-colored complete bipartite graph K_{n,n} is rainbow if no pair of edges in M have the same color. We obtain asymptotic enumeration results for the n…
On the tree-depth of Random Graphs
Guillem Perarnau, Oriol Serra
The tree-depth is a parameter introduced under several names as a measure of sparsity of a graph. We compute asymptotic values of the tree-depth of random graphs. For dense graphs,…
Bounds for identifying codes in terms of degree parameters
Florent Foucaud, Guillem Perarnau
An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. If $\M(G)$ denotes the minimum…