Typical T-free graphs

2025/06/01 by Bruce Reed, Reed, Bruce, Yelena Yuditsky +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2506.01067

Abstract

We prove that for every tree T which is not an edge, for almost every graph G which does not contain T as an induced subgraph, V(G) has a partition into α(T)-1 parts certifying this fact. Each part induces a graph which is P₄-free and has further properties which depend on T. As a consequence we obtain good bounds (often tight up to a constant factor) on the number of T-free graphs and show in a follow-up paper~\citeRY that almost every T-free graph G has chromatic number equal to the size of its largest clique.

Citations

• The Global Structure of a Typical Graph Without H as an Induced Subgraph when H is a Cycle
• Almost all string graphs are intersection graphs of plane convex sets
• Forbidding induced even cycles in a graph: typical structure and counting
• The structure of almost all graphs in a hereditary property
• On a Problem of Formal Logic

Related

• Square-free graphs with no six-vertex induced path
• Covering minimal separators and potential maximal cliques in P_t-free graphs
• Tree independence number V. Walls and claws
• Chromatic number of ISK4-free graphs
• Forbidden subgraphs and complete partitions