Journal article icon

Journal article

Random perfect graphs

Abstract:

We investigate the asymptotic structure of a random perfect graph $P_n$ sampled uniformly from the perfect graphs on vertex set $\{1,\ldots,n\}$. Our approach is based on the result of Pr\"omel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly. We show that the distribution of the maximum of the stability number $\alpha(P_n)$ and clique number $\omega(P_n)$ is close to a concentrated distribution $L(n)$ wh...

Expand abstract
Publication status:
Not published
Peer review status:
Not peer reviewed

Actions


Access Document


Files:

Authors


More by this author
Department:
Corpus Christi College
More by this author
Department:
Oxford, MPLS, Computer Science
Journal:
arXiv
Pubs id:
pubs:614625
URN:
uri:28dc3ea8-27b3-4a42-8143-725beb9becad
UUID:
uuid:28dc3ea8-27b3-4a42-8143-725beb9becad
Local pid:
pubs:614625

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP