Showing cs.DMShow all
2 papers · 1 filter
cs.DM2026
Adjacency labelling for proper minor-closed graph classes
Vida Dujmović, Cyril Gavoille, Gwenaël Joret +3
We show that every proper minor-closed class of graphs admits a -bit adjacency labelling scheme. Equivalently, for every proper minor-closed class a…
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…