Colin McDiarmid

According to our database1, Colin McDiarmid authored at least 125 papers between 1978 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 


Online presence:



Modularity of Erdős-Rényi random graphs.
Random Struct. Algorithms, 2020

Learning random points from geometric graphs or orderings.
Random Struct. Algorithms, 2020

Random perfect graphs.
Random Struct. Algorithms, 2019

Clique coloring of binomial random graphs.
Random Struct. Algorithms, 2019

On the purity of minor-closed classes of graphs.
J. Comb. Theory, Ser. B, 2019

On the critical densities of minor-closed classes.
Eur. J. Comb., 2019

Linear Extensions and Comparable Pairs in Partial Orders.
Order, 2018

Modularity of regular and treelike graphs.
J. Complex Networks, 2018

Clique Colourings of Geometric Graphs.
Electron. J. Comb., 2018

Uniform multicommodity flows in the hypercube with random edge-capacities.
Random Struct. Algorithms, 2017

Hamilton Cycles, Minimum Degree, and Bipartite Holes.
J. Graph Theory, 2017

Bridge-Addability, Edge-Expansion and Connectivity.
Comb. Probab. Comput., 2017

Random graphs from a block-stable class.
Eur. J. Comb., 2016

Connectivity for bridge-alterable graph classes.
Eur. J. Comb., 2016

Colour degree matrices of graphs with at most one cycle.
Discret. Appl. Math., 2016

Modularity of tree-like and random regular graphs.
CoRR, 2016

Random Graphs, Geometry and Asymptotic Structure.
London Mathematical Society student texts 84, Cambridge University Press, ISBN: 978-1-316-50191-7, 2016

Extremal Distances for Subtree Transfer Operations in Binary Trees.
CoRR, 2015

Recognition of Unipolar and Generalised Split Graphs.
Algorithms, 2015

Random graphs containing few disjoint excluded minors.
Random Struct. Algorithms, 2014

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

The number of disk graphs.
Eur. J. Comb., 2014

On the Spread of Random Graphs.
Comb. Probab. Comput., 2014

Uniform multicommodity flow in the hypercube with random edge capacities.
CoRR, 2014

Relatively Bridge-Addable Classes of Graphs.
Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Integer realizations of disk and segment graphs.
J. Comb. Theory, Ser. B, 2013

Modularity in random regular graphs and lattices.
Electron. Notes Discret. Math., 2013

On Independent Sets in Graphs with Given Minimum Degree.
Comb. Probab. Comput., 2013

Random Graphs from a Weighted Minor-Closed Class.
Electron. J. Comb., 2013

Connectivity for Bridge-Addable Monotone Graph Classes.
Comb. Probab. Comput., 2012

Connectivity for Random Graphs from a Weighted Bridge-Addable Class.
Electron. J. Comb., 2012

Quicksort and Large Deviations.
Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

Random unlabelled graphs containing few disjoint cycles.
Random Struct. Algorithms, 2011

Counting disk graphs.
Electron. Notes Discret. Math., 2011

Largest sparse subgraphs of random graphs.
Electron. Notes Discret. Math., 2011

On graphs with few disjoint t-star minors.
Eur. J. Comb., 2011

Random Graphs with Few Disjoint Cycles.
Comb. Probab. Comput., 2011

On the chromatic number of random geometric graphs.
Comb., 2011

Acyclic improper colourings of graphs with bounded maximum degree.
Discret. Math., 2010

The <i>t</i>-Improper Chromatic Number of Random Graphs.
Comb. Probab. Comput., 2010

The t-Stability Number of a Random Graph.
Electron. J. Comb., 2010

The Number of Bits Needed to Represent a Unit Disk Graph.
Proceedings of the Graph Theoretic Concepts in Computer Science, 2010

Random Hyperplane Search Trees.
SIAM J. Comput., 2009

Uniform multicommodity flow through the complete graph with random edge-capacities.
Oper. Res. Lett., 2009

Random Graphs from a Minor-Closed Class.
Comb. Probab. Comput., 2009

Random graphs on surfaces.
J. Comb. Theory, Ser. B, 2008

On the Maximum Degree of a Random Planar Graph.
Comb. Probab. Comput., 2008

Random cubic planar graphs.
Random Struct. Algorithms, 2007

The t-improper chromatic number of random graphs.
Electron. Notes Discret. Math., 2007

List Colouring Squares of Planar Graphs.
Electron. Notes Discret. Math., 2007

On The Span Of A Random Channel Assignment Problem.
Comb., 2007

Vertex-Colouring Edge-Weightings.
Comb., 2007

Concentration for self-bounding functions and an inequality of Talagrand.
Random Struct. Algorithms, 2006

Random planar graphs.
J. Comb. Theory, Ser. B, 2005

Random planar graphs with <i>n</i> nodes and a fixed number of edges.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Graph Imperfection with a Co-Site Constraint.
SIAM J. Discret. Math., 2004

On the Number of Edges in Random Planar Graphs.
Comb. Probab. Comput., 2004

Random channel assignment in the plane.
Random Struct. Algorithms, 2003

Channel assignment on graphs of bounded treewidth.
Discret. Math., 2003

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

Concentration for locally acting permutations.
Discret. Math., 2003

Upper bounds on the non-3-colourability threshold of random graphs.
Discret. Math. Theor. Comput. Sci., 2002

On the divisibility of graphs.
Discret. Math., 2002

Concentration For Independent Permutations.
Comb. Probab. Comput., 2002

Bisecting sparse random graphs.
Random Struct. Algorithms, 2001

Graph Imperfection II.
J. Comb. Theory, Ser. B, 2001

Graph Imperfection.
J. Comb. Theory, Ser. B, 2001

Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs.
Electron. Notes Discret. Math., 2001

Channel Assignment with Large Demands.
Ann. Oper. Res., 2001

Channel assignment and weighted coloring.
Networks, 2000

Frequency-distance constraints with large distances.
Discret. Math., 2000

Colouring proximity graphs in the plane.
Discret. Math., 1999

Pattern Minimisation in Cutting Stock Problems.
Discret. Appl. Math., 1999

Random Minimum Length Spanning Trees in Regular Graphs.
Comb., 1998

On finding a minimum spanning tree in a network with random weights.
Random Struct. Algorithms, 1997

Algorithmic theory of random graphs.
Random Struct. Algorithms, 1997

Hypergraph colouring and the Lovász Local Lemma.
Discret. Math., 1997

A Doubly Cyclic Channel Assignment Problem.
Discret. Appl. Math., 1997

Centering Sequences with Bounded Differences.
Comb. Probab. Comput., 1997

A random bit-flipping method for seeking agreement.
Random Struct. Algorithms, 1996

Edge-disjoint cycles in regular directed graphs.
J. Graph Theory, 1996

Tidier Examples for Lower Bounds on Diagonal Ramsey Numbers.
J. Comb. Theory, Ser. A, 1996

Large Deviations for Quicksort.
J. Algorithms, 1996

On the bandwidth of triangulated triangles.
Discret. Math., 1995

The Complexity of Harmonious Colouring for Trees.
Discret. Appl. Math., 1995

Almost Every Graph can be Covered by [fracDelta2] Linear Forests.
Comb. Probab. Comput., 1995

New upper bounds on harmonious colorings.
J. Graph Theory, 1994

Induced Circuits in Planar Graphs.
J. Comb. Theory, Ser. B, 1994

Total colouring regular bipartite graphs is NP-hard.
Discret. Math., 1994

Sharing jugs of wine.
Discret. Math., 1994

On Total Colorings of Graphs.
J. Comb. Theory, Ser. B, 1993

An upper bound for total colouring of graphs.
Discret. Math., 1993

A Random Recolouring Method for Graphs and Hypergrams.
Comb. Probab. Comput., 1993

Volumes Spanned by Random Points in the Hypercube.
Random Struct. Algorithms, 1992

The Strongly Connected Components of 1-in, 1-out.
Comb. Probab. Comput., 1992

On a Correlation Inequality of Farr.
Comb. Probab. Comput., 1992

On integer points in polyhedra.
Comb., 1992

Small transversals in hypergraphs.
Comb., 1992

Star arboricity.
Comb., 1992

Non-Interfering Network Flows.
Proceedings of the Algorithm Theory, 1992

Strong Concentration for Quicksort.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Acyclic Coloring of Graphs.
Random Struct. Algorithms, 1991

Upper bounds for harmonious colorings.
J. Graph Theory, 1991

Expected numbers at hitting times.
J. Graph Theory, 1991

Average Case Analysis of Heap Building by Repeated Insertion.
J. Algorithms, 1991

Lattice bandwidth of random graphs.
Discret. Appl. Math., 1991

An Expected-Cost Analysis of Backtracking and Non-Backtracking Algorithms.
Proceedings of the 12th International Joint Conference on Artificial Intelligence. Sydney, 1991

Greedy Matching on the Line.
SIAM J. Comput., 1990

Linear Arboricity of Random Regular Graphs.
Random Struct. Algorithms, 1990

On the Chromatic Number of Random Graphs.
Random Struct. Algorithms, 1990

On the Improvement per Iteration in Karmarkar's Algorithm for Linear Programming.
Math. Program., 1990

Random Volumes in the n-Cube.
Proceedings of the Polyhedral Combinatorics, 1990

Building Heaps Fast.
J. Algorithms, 1989

On random minimum lenght spanning trees.
Comb., 1989

Average-Case Lower Bounds for Searching.
SIAM J. Comput., 1988

Edge-colouring random graphs.
J. Comb. Theory, Ser. B, 1988

On the greedy algorithm with random costs.
Math. Program., 1986

On linear programs with random costs.
Math. Program., 1986

The Compexity of Counting Homeomorphs.
Theor. Comput. Sci., 1985

On some conditioning results in the probabilistic analysis of algorithms.
Discret. Appl. Math., 1985

Colouring random graphs.
Ann. Oper. Res., 1984

Integral decomposition in polyhedra.
Math. Program., 1983

On the chromatic forcing number of a random graph.
Discret. Appl. Math., 1983

Determining the Chromatic Number of a Graph.
SIAM J. Comput., 1979

Blocking, antiblocking, and pairs of matroids and polymatroids.
J. Comb. Theory, Ser. B, 1978