63 citations · 189 across the 26 of their papers we have counts for
6 papers · 2 filters
Edge-Maximal Graphs on Surfaces
Colin McDiarmid, David R. Wood
We prove that for every surface of Euler genus , every edge-maximal embedding of a graph in is at most edges short of a triangulation of . This provides the fi…
On the purity of minor-closed classes of graphs
Colin McDiarmid, Michał Przykucki
Given a graph with at least one edge, let denote the maximum difference between the numbers of edges in two -vertex edge-maximal graphs with no m…
Modularity of regular and treelike graphs
Colin McDiarmid, Fiona Skerman
Clustering algorithms for large networks typically use modularity values to test which partitions of the vertex set better represent structure in the data. The modularity of a grap…
Hamilton cycles, minimum degree and bipartite holes
Colin McDiarmid, Nikola Yolov
We present a tight extremal threshold for the existence of Hamilton cycles in graphs with large minimum degree and without a large ``bipartite hole`` (two disjoint sets of vertices…
Random Perfect Graphs
Colin McDiarmid, Nikola Yolov
We investigate the asymptotic structure of a random perfect graph sampled uniformly from the perfect graphs on vertex set . Our approach is based on the resul…
Linear Extensions and Comparable Pairs in Partial Orders
Colin McDiarmid, David Penman, Vasileios Iliopoulos
We study the number of linear extensions of a partial order with a given proportion of comparable pairs of elements, and estimate the maximum and minimum possible numbers. We also…