Excluding induced subgraphs: critical graphs

DOI10.1002/RSA.20353MaRDI QIDQ3068762zbMATH OpenOpenAlexFDO

Authors 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

critical graphsextremal graphsgraph countingstructure of \(H\)-free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Recommendations

• The asymptotic number of graphs not containing a fixed color-critical subgraph
• Exhaustive generation of \(k\)-critical \(\mathcal{H}\)-free graphs
• Extremal Graph Problems for Graphs with a Color-Critical Vertex
• Critical vertices and edges in \(H\)-free graphs
• Excluding Induced Subgraphs III: A General Asymptotic

Cites work

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

Cited in

(22)

• The asymptotic number of graphs not containing a fixed color-critical subgraph
• Critical vertices and edges in \(H\)-free graphs
• Forbidding induced even cycles in a graph: typical structure and counting
• Generalizations of independence and chromatic numbers of a graph
• 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
• The typical structure of maximal triangle-free graphs
• scientific article; zbMATH DE number 475587 (Why is no real title available?)
• Extremal Graph Problems for Graphs with a Color-Critical Vertex
• Almost all triangle-free triple systems are tripartite
• Random perfect graphs
• Almost all string graphs are intersection graphs of plane convex sets
• The regularity of almost all edge ideals
• The fine structure of octahedron-free graphs
• The structure of almost all graphs in a hereditary property
• For most graphs H, most H-free graphs have a linear homogeneous set
• On the typical structure of graphs not containing a fixed vertex-critical subgraph
• The typical structure of graphs with no large cliques
• Excluding induced subgraphs. II: Extremal graphs
• Typical structure of hereditary graph families. II: Exotic examples
• Typical structure of hereditary graph families. I: Apex-free families

This page was built for publication: Excluding induced subgraphs: critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068762)