Premium
Random perfect graphs
Author(s) -
McDiarmid Colin,
Yolov Nikola
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20770
Subject(s) - combinatorics , mathematics , split graph , chordal graph , indifference graph , random regular graph , discrete mathematics , vertex (graph theory) , random graph , perfect graph , degree (music) , trivially perfect graph , maximal independent set , induced subgraph , cograph , independent set , graph , pathwidth , 1 planar graph , line graph , physics , acoustics
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 Prömel 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 α ( P n ) and clique number ω ( P n ) 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 or1 2or 1. Further we show that almost all perfect graphs are 2‐clique‐colorable, improving a result of Bacsó et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity κ ( P n ) equal to their minimum degree; they are almost all in class one (edge‐colorable using Δ colors, where Δ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphonW P ( x , y ) = 1 2 ( 1 [ x ≤ 1 / 2 ] + 1 [ y ≤ 1 / 2 ] ) .