Abstract

Cographs are by definition $P_4$-free graphs, i.e. graphs avoiding the path $P_4$ as induced subgraph. In this talk, we will consider a uniform random cograph with $n$ vertices, for large $n$. We shall describe the (random) graphon limit of this object, which is constructed using a Brownian excursion. Motivated by some probabilistic work around Erdős-Hajnal conjecture, we also consider large independent sets in uniform cographs. For both aspects, cographs behave differently from most other $H$-free random graphs.

Based on joint work with F. Bassino, M. Bouvel, M. Drmota, L. Gerin, M. Maazoun and A. Pierrot.