Perfect Graphs of Fixed Density: Counting and Homogeneous Sets

DOI10.1017/S0963548312000181zbMath1248.05086arXiv1102.5229MaRDI QIDQ2911067

Andreas Würfl, Anusch Taraz, Julia Böttcher

Publication date: 12 September 2012

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.5229

zbMATH Keywords

graph density; embedding induced subgraphs

Mathematics Subject Classification ID

05C30: Enumeration in graph theory

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C17: Perfect graphs

05C42: Density (toughness, etc.)

Related Items

Random perfect graphs

Cites Work

• The structure of almost all graphs in a hereditary property
• The structure of hereditary properties and 2-coloured multigraphs
• Ramsey-type theorems
• The strong perfect graph theorem
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The number of graphs without forbidden subgraphs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Excluding induced subgraphs: quadrilaterals
• Excluding Induced Subgraphs III: A General Asymptotic
• On the entropy values of hereditary classes of graphs
• Almost all Berge Graphs are Perfect
• On the structure of linear graphs
• The structure of hereditary properties and colourings of random graphs
• Efficient testing of large graphs