The induced-$P_4$-free process

Abstract

We study the random induced-$P_4$-free graph process. Let $e_1,\ldots,e_N$, where $N=\binom{n}{2}$, be a uniformly random ordering of the edges of $K_n$. Starting from the empty graph $G_0$, we add $e_{m+1}$ whenever $G_m+e_{m+1}$ contains no induced $P_4$, and otherwise leave the graph unchanged. We show that the terminal graph is a trivially perfect graph and we describe the structure and distribution of the connected components of the terminal graph $G_N$. Consequently, we derive the limiting values of several natural graph parameters. In particular, the terminal graph $G_N$ has $Θ(n)$ edges.

Disclosure

“laws. 7 Acknowledgements This work was supported by the Key Program of the National Natural Science Foundation of China (NSFC) under Grant No. 12231018. 8 Declaration on the use of AI During the preparation of this manuscript, ChatGPT 5.6 was used to assist with computational tasks and language polishing. All research ideas, proof strategies, theoretical arguments, and conclusions were independently developed by the authors. References [1] F. Bassino, M. Bouvel, V. F”

PDF page 31

Classification

Computational experiments or data processing

Multiplier

3

Verified

2026-08-22T18:31:25.311644Z

Structural counts