Almost all chordal graphs split

Edward A. Bender, L. Bruce Richmond, N. C. Wormald · Journal of the Australian Mathematical Society Series A Pure Mathematics and Statistics · 1985

Abstract A chordal graph is a graph in which every cycle of length at least 4 has a chord. If G is a random n-vertex labelled chordal graph, the size of the larget clique in about n/2 and deletion of this clique almost surely leaves only isolated vertices. This gives the asymptotic number of chordal graphs and information about a variety of things such as the size of the largest clique and connectivity.

Read the paper · More papers on PaperTik