Random perfect graphs

DOI10.1002/RSA.20770MaRDI QIDQ4625032zbMATH OpenOpenAlexFDO

Authors Nikola Yolov, Colin McDiarmid

Publication date 20 February 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

clique coloringedge coloringgraph limitsHamiltonianperfect graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17) Random graphs (graph-theoretic aspects) (05C80)

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)$ 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 $frac12$ or $1$. Further we show that almost all perfect graphs are $2$-clique-colourable, improving a result of Bacs'o 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-colourable using $Delta$ colours, 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)=frac12(mathbb1[xle1/2]+mathbb1[yle1/2])$.

Recommendations

• The first order convergence law fails for random perfect graphs
• scientific article; zbMATH DE number 553912
• The first order convergence law fails for random perfect graphs
• Almost all Berge Graphs are Perfect
• A note on perfect graphs

Cites work

• A characterization of perfect graphs
• A constructive proof of Vizing's theorem
• Almost all Berge Graphs are Perfect
• Clique coloring of binomial random graphs
• Coloring the Maximal Cliques of Graphs
• Edge-colouring random graphs
• Excluding induced subgraphs: critical graphs
• Hamilton cycles, minimum degree, and bipartite holes
• scientific article; zbMATH DE number 3134390 (Why is no real title available?)
• scientific article; zbMATH DE number 19173 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• scientific article; zbMATH DE number 3273761 (Why is no real title available?)
• Large networks and graph limits
• Limit distribution for the existence of Hamiltonian cycles in random bipartite graphs
• Normal hypergraphs and the perfect graph conjecture
• On the chromatic index of almost all graphs
• Perfect graphs of arbitrarily large clique-chromatic number
• Perfect graphs of fixed density: counting and homogeneous sets
• Random graphs.
• Random set partitions: Asymptotics of subset counts
• Recognition of unipolar and generalised split graphs
• Stirling Behavior is Asymptotically Normal
• The structure of almost all graphs in a hereditary property
• Two-colouring all two-element maximal antichains

Cited in

(7)

• On randomized stopping points and perfect graphs
• The first order convergence law fails for random perfect graphs
• Independent sets, cliques, and colorings in graphons
• Perfect graphs of fixed density: counting and homogeneous sets
• The first order convergence law fails for random perfect graphs
• Random cographs: Brownian graphon limit and asymptotic degree distribution
• Dense and nondense limits for uniform random intersection graphs

This page was built for publication: Random perfect graphs

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