2025/06/04 by Bruce H. Reed, Reed, Bruce
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2506.03544
openalex publication_date 2025/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One way to certify that a graph does not contain an induced cycle of length six is to provide a partition of its vertex set into (i) a stable set, and (ii) a graph containing no stable set of size three and no induced matching of size two. We show that almost every graph which does not contain a cycle of length six as an induced subgraph has such a certificate. We obtain similar characterizations of the structure of almost all graphs which contain no induced cycle of length k for all even k exceeding six. (Similar results were obtained for k=3 by Erdos, Kleitman, and Rothschild in 1976, for k =4,5 by Promel and Steger in 1991 and for odd k exceeding 5 by Balogh and Butterfield in 2009.) We prove that a simiiar theorem for all H holds up to the deletion of a set of o(|V(G)|) vertices and ask for which H the characterization holds fully.