2020/07/01 by Sergey Norin, Norin, Sergey, Yelena Yuditsky +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2007.00688
openalex publication_date 2020/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is H-free if it does not contain an induced subgraph isomorphic to H. The study of the typical structure of H-free graphs was initiated by Erdős, Kleitman and Rothschild, who have shown that almost all C3-free graphs are bipartite. Since then the typical structure of H-free graphs has been determined for several families of graphs H, including complete graphs, trees and cycles. Recently, Reed and Scott proposed a conjectural description of the typical structure of H-free graphs for all graphs H, which extends all previously known results in the area. We construct an infinite family of graphs for which the Reed-Scott conjecture fails, and use the methods we developed in the prequel paper to describe the typical structure of H-free graphs for graphs H in this family. Using similar techniques, we construct an infinite family of graphs H for which the maximum size of a homogenous set in a typical H-free graph is sublinear in the number of vertices, answering a question of Loebl et al. and Kang et al.