View abstract

Session I.3 - Graph Theory and Combinatorics - Semi-plenary talk

Tuesday, June 13, 17:30 ~ 18:30

Graph classes and their Asymptotic Dimension

Marthe Bonamy

CNRS, Université de Bordeaux, France   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Introduced in 1993 by Gromov in the context of geometric group theory, the asymptotic dimension of a graph class measures how much ``contact'' is necessary between balls of ``bounded'' diameter covering a graph in that class. This concept has connections with clustered coloring or weak diameter network decompositions. While it seems surprisingly fundamental, much remains unknown about this parameter and it displays intriguing behaviours. We will provide a gentle exposition to the area: from the state of the art to the main tools and questions, including some answers. We will introduce and discuss minors in graphs and related concepts.

View abstract PDF