Paper Info
Title
Random perfect graphs.
Abstract
We investigate the asymptotic structure of a random perfect graph P-n sampled uniformly from the set of perfect graphs on vertex set {1,...,n}. Our approach is based on the result of Promel 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(Pn) and clique number omega(Pn) is close to a concentrated distribution L(n) which plays an important role in our generation method. We also prove that the probability that P-n contains any given graph H as an induced subgraph is asymptotically 0 or 1/2 or 1. Further we show that almost all perfect graphs are 2-clique-colorable, improving a result of Bacso et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity kappa(P-n) equal to their minimum degree; they are almost all in class one (edge-colorable using Delta colors, where Delta is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphon W-P(x,y) = 1/2 (1[x <= 1/2] + 1[y <= 1/2]).
Year
DOI
Venue
2019
10.1002/rsa.20770
RANDOM STRUCTURES & ALGORITHMS
Keywords
DocType
Volume
Clique-coloring,edge-coloring,graph limits,Hamiltonian,perfect graphs
Journal
54.0
Issue
ISSN
Citations 
1.0
1042-9832
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Colin McDiarmid11071167.05
Nikola Yolov272.05