11 citations · 17 across the 16 of their papers we have counts for
5 papers · 1 filter
Tight bounds on adjacency labels for monotone graph classes
Édouard Bonnet, Julien Duron, John Sylvester +2
A class of graphs admits an adjacency labeling scheme of size , if the vertices in each of its -vertex graphs can be assigned binary strings (called labels) of length $b(n…
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank
Nathaniel Harms, Viktor Zamaraev
We prove a characterization of the structural conditions on matrices of sign-rank 3 and unit disk graphs (UDGs) which permit constant-cost public-coin randomized communication prot…
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
Édouard Bonnet, Julien Duron, John Sylvester +2
We show that for any natural number , there is a constant and a subgraph-closed class having, for any natural , at most graphs on vertices up to isomorphism, bu…
Graphs with minimum fractional domatic number
Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios +1
The domatic number of a graph is the maximum number of vertex disjoint dominating sets that partition the vertex set of the graph. In this paper we consider the fractional variant…
Functionality of box intersection graphs
Clément Dallard, Vadim Lozin, Martin Milanič +2
Functionality is a graph complexity measure that extends a variety of parameters, such as vertex degree, degeneracy, clique-width, or twin-width. In the present paper, we show that…