Perfect graphs of fixed density: counting and homogeneous sets

DOI10.1017/S0963548312000181MaRDI QIDQ2911067zbMATH OpenFDO

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

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

embedding induced subgraphsgraph density

Mathematics Subject Classification ID

Perfect graphs (05C17) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: For c in [0,1] let P_n(c) denote the set of n-vertex perfect graphs with density c and C_n(c) the set of n-vertex graphs without induced C_5 and with density c. We show that log|P_n(c)|/binom{n}{2}=log|C_n(c)|/binom{n}{2}=h(c)+o(1) with h(c)=1/2 if 1/4<c<3/4 and h(c)=H(|2c-1|)/2 otherwise, where H is the binary entropy function. Further, we use this result to deduce that almost all graphs in C_n(c) have homogenous sets of linear size. This answers a question raised by Loebl, Reed, Scott, Thomason, and Thomass'e [Almost all H-free graphs have the ErdH{o}s-Hajnal property] in the case of forbidden induced C_5.

Recommendations

• Induced C₅-free graphs of fixed density: counting and homogeneous sets
• Random perfect graphs
• On the number of homogeneous subgraphs of a graph
• Almost all Berge Graphs are Perfect
• scientific article; zbMATH DE number 970795

Cites work

• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Almost all Berge Graphs are Perfect
• Efficient testing of large graphs
• Excluding Induced Subgraphs III: A General Asymptotic
• Excluding induced subgraphs: quadrilaterals
• On the entropy values of hereditary classes of graphs
• On the structure of linear graphs
• Ramsey-type theorems
• 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
• The strong perfect graph theorem
• The structure of almost all graphs in a hereditary property
• The structure of hereditary properties and 2-coloured multigraphs
• The structure of hereditary properties and colourings of random graphs

Cited in

(6)

• The set of ratios of derangements to permutations in digraphs is dense in \([0,1/2]\)
• Induced C₅-free graphs of fixed density: counting and homogeneous sets
• scientific article; zbMATH DE number 1735658 (Why is no real title available?)
• Random perfect graphs
• Threshold graphs maximise homomorphism densities
• Consistent random vertex-orderings of graphs

This page was built for publication: Perfect graphs of fixed density: counting and homogeneous sets

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