Graph classes with few $P_4$'s: Universality and Brownian graphon limits - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... (Preprint) Year :

## Graph classes with few $P_4$'s: Universality and Brownian graphon limits

Théo Lenoir
• Function : Author
• PersonId : 1219716

#### Abstract

We consider large uniform labeled random graphs in different classes with few induced $P_4$ ($P_4$ is the graph consisting of a single line of $4$ vertices), which generalize the case of cographs. Our main result is the convergence to a Brownian limit object in the space of graphons. We also obtain an equivalent of the number of graphs of size $n$ in the different classes. Finally we estimate the expected number of induced graphs isomorphic to a fixed graph $H$ for a large variety of graphs $H$. Our proofs rely on tree encoding of graphs. We then use mainly combinatorial arguments, including the symbolic method and singularity analysis.

### Dates and versions

hal-03956705 , version 1 (26-01-2023)
hal-03956705 , version 2 (17-02-2023)

### Identifiers

• HAL Id : hal-03956705 , version 1

### Cite

Théo Lenoir. Graph classes with few $P_4$'s: Universality and Brownian graphon limits. 2023. ⟨hal-03956705v1⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite
1 View