Colin McDiarmid

According to our database, Colin McDiarmid authored at least 134 papers between 1978 and 2026.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2026

Note on edge expansion and modularity in preferential attachment graphs.

Colin McDiarmid, Katarzyna Rybarczyk, Fiona Skerman, Malgorzata Sulkowska

CoRR, January, 2026

2025

Modularity and random graphs.

Colin McDiarmid, Fiona Skerman

CoRR, September, 2025

2024

Random graphs embeddable in order-dependent surfaces.

Colin McDiarmid, Sophia Saller

Random Struct. Algorithms, July, 2024

Pendant appearances and components in random graphs from structured classes.

Colin McDiarmid

Eur. J. Comb., 2024

Modularity and Graph Expansion.

Baptiste Louf, Colin McDiarmid, Fiona Skerman

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Modularity of very dense graphs.

Colin McDiarmid, Fiona Skerman

CoRR, 2023

Classes of graphs embeddable in order-dependent surfaces.

Colin McDiarmid, Sophia Saller

Comb. Theory, 2023

2021

The component structure of dense random subgraphs of the hypercube.

Colin McDiarmid, Alex Scott, Paul Withers

Random Struct. Algorithms, 2021

Modularity and edge sampling.

Colin McDiarmid, Fiona Skerman

CoRR, 2021

2020

Learning random points from geometric graphs or orderings.

Josep Díaz, Colin McDiarmid, Dieter Mitsche

Random Struct. Algorithms, 2020

2019

Random perfect graphs.

Colin McDiarmid, Nikola Yolov

Random Struct. Algorithms, 2019

Clique coloring of binomial random graphs.

Colin McDiarmid, Dieter Mitsche, Pawel Pralat

Random Struct. Algorithms, 2019

On the purity of minor-closed classes of graphs.

Colin McDiarmid, Michal Przykucki

J. Comb. Theory B, 2019

On the critical densities of minor-closed classes.

Colin McDiarmid, Michal Przykucki

Eur. J. Comb., 2019

2018

Linear Extensions and Comparable Pairs in Partial Orders.

Colin McDiarmid, David B. Penman, Vasileios Iliopoulos

Order, 2018

Modularity of regular and treelike graphs.

Colin McDiarmid, Fiona Skerman

J. Complex Networks, 2018

Clique Colourings of Geometric Graphs.

Colin McDiarmid, Dieter Mitsche, Pawel Pralat

Electron. J. Comb., 2018

Modularity of Erdös-Rényi Random Graphs.

Colin McDiarmid, Fiona Skerman

Proceedings of the 29th International Conference on Probabilistic, 2018

2017

Uniform multicommodity flows in the hypercube with random edge-capacities.

Colin McDiarmid, Alex Scott, Paul Withers

Random Struct. Algorithms, 2017

Hamilton Cycles, Minimum Degree, and Bipartite Holes.

Colin McDiarmid, Nikola Yolov

J. Graph Theory, 2017

Bridge-Addability, Edge-Expansion and Connectivity.

Colin McDiarmid, Kerstin Weller

Comb. Probab. Comput., 2017

2016

Random graphs from a block-stable class.

Colin McDiarmid, Alex Scott

Eur. J. Comb., 2016

Connectivity for bridge-alterable graph classes.

Colin McDiarmid

Eur. J. Comb., 2016

Colour degree matrices of graphs with at most one cycle.

A. Hillebrand, Colin McDiarmid

Discret. Appl. Math., 2016

Modularity of tree-like and random regular graphs.

Colin McDiarmid, Fiona Skerman

CoRR, 2016

Random Graphs, Geometry and Asymptotic Structure.

Michael Krivelevich, Konstantinos Panagiotou, Mathew D. Penrose, Colin J. H. McDiarmid

London Mathematical Society student texts 84, Cambridge University Press, ISBN: 978-1-316-50191-7, 2016

2015

Extremal Distances for Subtree Transfer Operations in Binary Trees.

Ross Atkins, Colin McDiarmid

CoRR, 2015

Recognition of Unipolar and Generalised Split Graphs.

Colin McDiarmid, Nikola Yolov

Algorithms, 2015

2014

Random graphs containing few disjoint excluded minors.

Colin McDiarmid, Valentas Kurauskas

Random Struct. Algorithms, 2014

For most graphs <i>H</i>, most <i>H</i>-free graphs have a linear homogeneous set.

Ross J. Kang, Colin McDiarmid, Bruce A. Reed, Alex D. Scott

Random Struct. Algorithms, 2014

The number of disk graphs.

Colin McDiarmid, Tobias Müller

Eur. J. Comb., 2014

On the Spread of Random Graphs.

Louigi Addario-Berry, Svante Janson, Colin McDiarmid

Comb. Probab. Comput., 2014

Uniform multicommodity flow in the hypercube with random edge capacities.

Colin McDiarmid, Alex D. Scott, Paul Withers

CoRR, 2014

Relatively Bridge-Addable Classes of Graphs.

Colin McDiarmid, Kerstin Weller

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

2013

Integer realizations of disk and segment graphs.

Colin McDiarmid, Tobias Müller

J. Comb. Theory B, 2013

Modularity in random regular graphs and lattices.

Colin McDiarmid, Fiona Skerman

Electron. Notes Discret. Math., 2013

On Independent Sets in Graphs with Given Minimum Degree.

Hiu-Fai Law, Colin McDiarmid

Comb. Probab. Comput., 2013

Random Graphs from a Weighted Minor-Closed Class.

Colin McDiarmid

Electron. J. Comb., 2013

2012

Connectivity for Bridge-Addable Monotone Graph Classes.

Louigi Addario-Berry, Colin McDiarmid, Bruce A. Reed

Comb. Probab. Comput., 2012

Connectivity for Random Graphs from a Weighted Bridge-Addable Class.

Colin McDiarmid

Electron. J. Comb., 2012

Quicksort and Large Deviations.

Colin McDiarmid

Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

2011

Random unlabelled graphs containing few disjoint cycles.

Mihyun Kang, Colin McDiarmid

Random Struct. Algorithms, 2011

Counting disk graphs.

Colin McDiarmid, Tobias Müller

Electron. Notes Discret. Math., 2011

Largest sparse subgraphs of random graphs.

Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid

Electron. Notes Discret. Math., 2011

On graphs with few disjoint t-star minors.

Colin McDiarmid

Eur. J. Comb., 2011

Random Graphs with Few Disjoint Cycles.

Valentas Kurauskas, Colin McDiarmid

Comb. Probab. Comput., 2011

On the chromatic number of random geometric graphs.

Colin McDiarmid, Tobias Müller

Comb., 2011

2010

Acyclic improper colourings of graphs with bounded maximum degree.

Louigi Addario-Berry, Louis Esperet, Ross J. Kang, Colin J. H. McDiarmid, Alexandre Pinlou

Discret. Math., 2010

The <i>t</i>-Improper Chromatic Number of Random Graphs.

Ross J. Kang, Colin McDiarmid

Comb. Probab. Comput., 2010

The t-Stability Number of a Random Graph.

Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid

Electron. J. Comb., 2010

The Number of Bits Needed to Represent a Unit Disk Graph.

Colin McDiarmid, Tobias Müller

Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

2009

Random Hyperplane Search Trees.

Luc Devroye, James King, Colin McDiarmid

SIAM J. Comput., 2009

Uniform multicommodity flow through the complete graph with random edge-capacities.

David J. Aldous, Colin McDiarmid, Alex D. Scott

Oper. Res. Lett., 2009

Random Graphs from a Minor-Closed Class.

Colin McDiarmid

Comb. Probab. Comput., 2009

2008

Random graphs on surfaces.

Colin McDiarmid

J. Comb. Theory B, 2008

On the Maximum Degree of a Random Planar Graph.

Colin McDiarmid, Bruce A. Reed

Comb. Probab. Comput., 2008

2007

Random cubic planar graphs.

Manuel Bodirsky, Mihyun Kang, Mike Löffler, Colin McDiarmid

Random Struct. Algorithms, 2007

The t-improper chromatic number of random graphs.

Ross J. Kang, Colin J. H. McDiarmid

Electron. Notes Discret. Math., 2007

List Colouring Squares of Planar Graphs.

Frédéric Havet, Jan van den Heuvel, Colin McDiarmid, Bruce A. Reed

Electron. Notes Discret. Math., 2007

On The Span Of A Random Channel Assignment Problem.

Colin McDiarmid

Comb., 2007

Vertex-Colouring Edge-Weightings.

Louigi Addario-Berry, Ketan Dalal, Colin McDiarmid, Bruce A. Reed, Andrew Thomason

Comb., 2007

2006

Concentration for self-bounding functions and an inequality of Talagrand.

Colin McDiarmid, Bruce A. Reed

Random Struct. Algorithms, 2006

2005

Random planar graphs.

Colin McDiarmid, Angelika Steger, Dominic J. A. Welsh

J. Comb. Theory B, 2005

Random planar graphs with <i>n</i> nodes and a fixed number of edges.

Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weißl

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Graph Imperfection with a Co-Site Constraint.

Stefanie Gerke, Colin McDiarmid

SIAM J. Discret. Math., 2004

On the Number of Edges in Random Planar Graphs.

Stefanie Gerke, Colin McDiarmid

Comb. Probab. Comput., 2004

2003

Random channel assignment in the plane.

Colin McDiarmid

Random Struct. Algorithms, 2003

Channel assignment on graphs of bounded treewidth.

Colin McDiarmid, Bruce A. Reed

Discret. Math., 2003

On the span in channel assignment problems: bounds, computing and counting.

Colin J. H. McDiarmid

Discret. Math., 2003

Concentration for locally acting permutations.

Malwina J. Luczak, Colin J. H. McDiarmid

Discret. Math., 2003

2002

Upper bounds on the non-3-colourability threshold of random graphs.

Nikolaos Fountoulakis, Colin McDiarmid

Discret. Math. Theor. Comput. Sci., 2002

On the divisibility of graphs.

Chính T. Hoàng, Colin J. H. McDiarmid

Discret. Math., 2002

Concentration For Independent Permutations.

Colin McDiarmid

Comb. Probab. Comput., 2002

2001

Bisecting sparse random graphs.

Malwina J. Luczak, Colin McDiarmid

Random Struct. Algorithms, 2001

Graph Imperfection II.

Stefanie Gerke, Colin McDiarmid

J. Comb. Theory B, 2001

Graph Imperfection.

Stefanie Gerke, Colin McDiarmid

J. Comb. Theory B, 2001

Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs.

Colin McDiarmid, Bruce A. Reed

Electron. Notes Discret. Math., 2001

Channel Assignment with Large Demands.

Stefanie Gerke, Colin McDiarmid

Ann. Oper. Res., 2001

2000

Channel assignment and weighted coloring.

Colin McDiarmid, Bruce A. Reed

Networks, 2000

Frequency-distance constraints with large distances.

Colin J. H. McDiarmid

Discret. Math., 2000

1999

Colouring proximity graphs in the plane.

Colin McDiarmid, Bruce A. Reed

Discret. Math., 1999

Pattern Minimisation in Cutting Stock Problems.

Colin McDiarmid

Discret. Appl. Math., 1999

1998

Random Minimum Length Spanning Trees in Regular Graphs.

Andrew Beveridge, Alan M. Frieze, Colin McDiarmid

Comb., 1998

1997

On finding a minimum spanning tree in a network with random weights.

Colin McDiarmid, Theodore Johnson, Harold S. Stone

Random Struct. Algorithms, 1997

Algorithmic theory of random graphs.

Alan M. Frieze, Colin McDiarmid

Random Struct. Algorithms, 1997

Hypergraph colouring and the Lovász Local Lemma.

Colin McDiarmid

Discret. Math., 1997

A Doubly Cyclic Channel Assignment Problem.

Colin McDiarmid

Discret. Appl. Math., 1997

Centering Sequences with Bounded Differences.

Colin McDiarmid

Comb. Probab. Comput., 1997

1996

A random bit-flipping method for seeking agreement.

Colin McDiarmid

Random Struct. Algorithms, 1996

Edge-disjoint cycles in regular directed graphs.

Noga Alon, Colin McDiarmid, Michael Molloy

J. Graph Theory, 1996

Tidier Examples for Lower Bounds on Diagonal Ramsey Numbers.

Colin McDiarmid, Angelika Steger

J. Comb. Theory A, 1996

Large Deviations for Quicksort.

Colin McDiarmid, Ryan Hayward

J. Algorithms, 1996

1995

On the bandwidth of triangulated triangles.

Robert Hochberg, Colin McDiarmid, Michael E. Saks

Discret. Math., 1995

The Complexity of Harmonious Colouring for Trees.

Keith Edwards, Colin McDiarmid

Discret. Appl. Math., 1995

Almost Every Graph can be Covered by [fracDelta2] Linear Forests.

Colin McDiarmid, Bruce A. Reed

Comb. Probab. Comput., 1995

1994

New upper bounds on harmonious colorings.

Keith Edwards, Colin McDiarmid

J. Graph Theory, 1994

Induced Circuits in Planar Graphs.

Colin J. H. McDiarmid, Bruce A. Reed, Alexander Schrijver, F. Bruce Shepherd

J. Comb. Theory B, 1994

Total colouring regular bipartite graphs is NP-hard.

Colin J. H. McDiarmid, Abdón Sánchez-Arroyo

Discret. Math., 1994

Sharing jugs of wine.

Colin J. H. McDiarmid, Jorge L. Ramírez Alfonsín

Discret. Math., 1994

1993

On Total Colorings of Graphs.

Colin J. H. McDiarmid, Bruce A. Reed

J. Comb. Theory B, 1993

An upper bound for total colouring of graphs.

Colin J. H. McDiarmid, Abdón Sánchez-Arroyo

Discret. Math., 1993

A Random Recolouring Method for Graphs and Hypergrams.

Colin McDiarmid

Comb. Probab. Comput., 1993

1992

Volumes Spanned by Random Points in the Hypercube.

Martin E. Dyer, Zoltán Füredi, Colin McDiarmid

Random Struct. Algorithms, 1992

The Strongly Connected Components of 1-in, 1-out.

Bruce A. Reed, Colin McDiarmid

Comb. Probab. Comput., 1992

On a Correlation Inequality of Farr.

Colin McDiarmid

Comb. Probab. Comput., 1992

On integer points in polyhedra.

William J. Cook, Mark Hartmann, Ravi Kannan, Colin McDiarmid

Comb., 1992

Small transversals in hypergraphs.

Vasek Chvátal, Colin McDiarmid

Comb., 1992

Star arboricity.

Noga Alon, Colin McDiarmid, Bruce A. Reed

Comb., 1992

Non-Interfering Network Flows.

Colin McDiarmid, Bruce A. Reed, Alexander Schrijver, F. Bruce Shepherd

Proceedings of the Algorithm Theory, 1992

Strong Concentration for Quicksort.

Colin McDiarmid, Ryan Hayward

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

Acyclic Coloring of Graphs.

Noga Alon, Colin McDiarmid, Bruce A. Reed

Random Struct. Algorithms, 1991

Upper bounds for harmonious colorings.

Colin McDiarmid, Luo Xinhua

J. Graph Theory, 1991

Expected numbers at hitting times.

Colin McDiarmid

J. Graph Theory, 1991

Average Case Analysis of Heap Building by Repeated Insertion.

Ryan Hayward, Colin McDiarmid

J. Algorithms, 1991

Lattice bandwidth of random graphs.

Colin McDiarmid, Zevi Miller

Discret. Appl. Math., 1991

An Expected-Cost Analysis of Backtracking and Non-Backtracking Algorithms.

Colin J. H. McDiarmid, Gregory M. Provan

Proceedings of the 12th International Joint Conference on Artificial Intelligence. Sydney, 1991

1990

Greedy Matching on the Line.

Alan M. Frieze, Colin McDiarmid, Bruce A. Reed

SIAM J. Comput., 1990

Linear Arboricity of Random Regular Graphs.

Colin McDiarmid, Bruce A. Reed

Random Struct. Algorithms, 1990

On the Chromatic Number of Random Graphs.

Colin McDiarmid

Random Struct. Algorithms, 1990

On the Improvement per Iteration in Karmarkar's Algorithm for Linear Programming.

Colin McDiarmid

Math. Program., 1990

Random Volumes in the n-Cube.

Martin E. Dyer, Zoltán Füredi, Colin McDiarmid

Proceedings of the Polyhedral Combinatorics, 1990

1989

Building Heaps Fast.

Colin McDiarmid, Bruce A. Reed

J. Algorithms, 1989

On random minimum lenght spanning trees.

Alan M. Frieze, Colin J. H. McDiarmid

Comb., 1989

1988

Average-Case Lower Bounds for Searching.

Colin McDiarmid

SIAM J. Comput., 1988

Edge-colouring random graphs.

Alan M. Frieze, Bill Jackson, Colin J. H. McDiarmid, Bruce A. Reed

J. Comb. Theory B, 1988

1986

On the greedy algorithm with random costs.

Colin McDiarmid

Math. Program., 1986

On linear programs with random costs.

Martin E. Dyer, Alan M. Frieze, Colin J. H. McDiarmid

Math. Program., 1986

1985

The Compexity of Counting Homeomorphs.

Graham Farr, Colin McDiarmid

Theor. Comput. Sci., 1985

On some conditioning results in the probabilistic analysis of algorithms.

Colin McDiarmid

Discret. Appl. Math., 1985

1984

Colouring random graphs.

Colin McDiarmid

Ann. Oper. Res., 1984

1983

Integral decomposition in polyhedra.

Colin McDiarmid

Math. Program., 1983

On the chromatic forcing number of a random graph.

Colin McDiarmid

Discret. Appl. Math., 1983

1979

Determining the Chromatic Number of a Graph.

Colin McDiarmid

SIAM J. Comput., 1979

1978

Blocking, antiblocking, and pairs of matroids and polymatroids.

Colin McDiarmid

J. Comb. Theory B, 1978