Excluding induced subgraphs: Critical graphs

DOI10.1002/rsa.20353zbMath1225.05138MaRDI QIDQ3068762

József Balogh, Jane V. Butterfield

Publication date: 17 January 2011

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20353

zbMATH Keywords

extremal graphs; critical graphs; graph counting; structure of \(H\)-free graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

Related Items

Random perfect graphs, Almost all string graphs are intersection graphs of plane convex sets, Almost all triangle-free triple systems are tripartite, The fine structure of octahedron-free graphs, The structure of almost all graphs in a hereditary property, The typical structure of graphs with no large cliques, Forbidding induced even cycles in a graph: typical structure and counting, Almost all string graphs are intersection graphs of plane convex sets, Almost all triple systems with independent neighborhoods are semi-bipartite, The typical structure of sparse $K_{r+1}$-free graphs, For most graphs H , most H -free graphs have a linear homogeneous set, THE TYPICAL STRUCTURE OF MAXIMAL TRIANGLE-FREE GRAPHS

Cites Work

• Unnamed Item
• The maximum edit distance from hereditary graph properties
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• On the size of hereditary classes of graphs
• The number of graphs without forbidden subgraphs
• The speed of hereditary properties of graphs
• The typical structure of graphs without given excluded subgraphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Excluding Induced Subgraphs III: A General Asymptotic
• Almost all Berge Graphs are Perfect
• Projections of Bodies and Hereditary Properties of Hypergraphs