Recent Advances in Adjacency Labeling Schemes

21^st October 2026, 13:00 GH223
Viktor Zamaraev
University of Liverpool

Abstract

Adjacency labeling schemes provide a local representation of graphs: each vertex is assigned a short label, and adjacency between two vertices can be determined solely from their labels. In this talk, I will survey recent advances in adjacency labeling schemes, with a particular emphasis on small graph classes. I will highlight new positive results that establish efficient labeling schemes for broad families of such classes, as well as recent lower bounds that reveal fundamental limitations of these representations. The talk will outline several directions for future work.