Professor McDiarmid Publications
For availability of items which are not online, please contact the Professorial Secretary Mrs. Christine Stone
Publications
2008
Colin McDiarmid, Random graphs on surfaces, J. Combinatorial Theory B 98 (2008) 778-797.
Colin McDiarmid and Bruce Reed, On the maximum degree of a random planar graph, Combinatorics, Probability and Computing 17 (2008) 591-601
2007
Colin McDiarmid. On the span of a random channel assignment problem, Combinatorica 27 (2007) 183-203
Louigi Addario-Berry, Ketan Dalal, Colin McDiarmid, Bruce A. Reed, Andrew Thomason. Vertex-colouring edge-weightings, Combinatorica 27 (1)(2007) 1-12
Malwina J Luczak, Colin McDiarmid. Asymptotic distributions and chaos for the supermarket model, Electronic Journal of Probability 12 (2007) 75-99
Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weissl. Random planar graphs with given average degree, Combinatorics, Complexity and Chance, a tribute to Dominic Welsh (editors: G. Grimmett and C. McDiarmid) Oxford University Press, 2007, 83-102
Manuel Bodirsky, Mihyun Kang, Mike Loeffler, Colin McDiarmid. Random cubic planar graphs, Random Structures and Algorithms 30 (2007) 78-94
Ross Kang, Colin McDiarmid. The t-improper chromatic number of random graphs, Eurocomb07, Electronic Notes in Discrete Mathematics 29 (2007) 411-417
Frederic Havet, Jan van den Heuvel Colin McDiarmid, Bruce Reed. List colouring squares of planar graphs, Eurocomb07, Electronic Notes in Discrete Mathematics 29 (2007) 515-519
2006
Colin McDiarmid, Bruce Reed. Concentration for self-bounding functions and an inequality of Talagrand, Random Structures and Algorithms 29 (2006) 549-557
Colin McDiarmid, Angelika Steger, Dominic Welsh. Random Graphs from planar and other addable classes, Topics in Discrete Mathematics (editors: M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, P. Valtr), Algorithms and Combinatorics 26 Springer, 2006, 231-246
Malwina J. Luczak, Colin McDiarmid. On the maximum queue length in the supermarket model, Annals of Probability 34, 493-527
2005
C.J.H. McDiarmid, T. Muller. Colouring random geometric graphs, EuroComb 2005, Discrete Mathematics and Theoretical Computer Science Proceedings AE (2005) 1-4.
Malwina J. Luczak, Colin McDiarmid. On the power of two choices: balls and bins in continuous time, The Annals of Applied Probability 2005, 15, No. 3, 1733-1764
Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weissl. Random planar graphs with n nodes and a fixed number of edges, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2005, 999-1007
Colin McDiarmid, Angelika Steger, Dominic J.A. Welsh. Random planar graphs, J Combinatorial Theory B 93 (2005) 187-206
2004
Stefanie Gerke, Colin McDiarmid. On the number of edges in random planar graphs, Combinatorics, Probability and Computing 13 (2004) 165-183
Stefanie Gerke, Colin McDiarmid. Graph imperfection with a co-site constraint, SIAM Journal on Discrete Mathematics 17 (2004) 403-425
2003
Colin McDiarmid. Channel assignment and discrete mathematics, Recent Advances in Algorithms and Combinatorics, B.A. Reed and C. L. Sales, editors, Springer, 2003, 27-63
Colin McDiarmid. Random channel assignment in the plane, Random Structures and Algorithms (2003) 187-212
Malwina J. Luczak, Colin McDiarmid. Concentration for locally acting permutations, Discrete Mathematics 265 (2003) 159-171
Colin McDiarmid, Bruce Reed. Channel assignment on graphs of bounded treewidth, Discrete Mathematics 273 (2003) 183-192 (Special issue: Eurocomb01 - Edited by J. Nesetril, M. Noy and O. Serra)
Colin McDiarmid. On the span in channel assignment problems: bounds, computing and counting, Discrete Mathematics 266 (2003) 387-397
Malwina J. Luczak, Colin McDiarmid, Eli Upfal. On-Line routing of random calls in networks, Probability Theory and Related Fields 125 (2003) 457-482
2002
Chinh Hoang, Colin McDiarmid. On the divisibility of graphs, Discrete Mathematics 242 (2002) 145-156
Luc Devroye, Colin McDiarmid, Bruce Reed. Giant components for two expanding graph processes, Proceedings of the Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Versailles, Mathematics and Computer Science II Algorithms, Trees, Combinatorics and Probability, September 2002: (editors B. Chauvin, P. Flajolet, D. Gardy and A. Mokkadem, Birkhauser-Verlag) Basel, (2002) 161-173
Jan van den Heuvel, Colin McDiarmid. Channel assignment on infinite sets under frequency-distance constraints, ( R.A. Leese and S. Hurley editors) Methods and Algorithms for Radio Channel Assignment, Oxford University Press, (2002) 63-87
Nikolaos Fountoulakis, Colin McDiarmid. Improved bounds for the non-3-colourability threshold in random graphs, Discrete Mathematics and Theoretical Computer Science, (2002) 205-226
Colin McDiarmid. Concentration for independent permutations, Combinatorics, Probability and Computing, (2002) 163-178
2001
Stefanie Gerke, Colin McDiarmid. Channel assignment with large demands, Annals of Operations Research (2001) 143-159
Stefanie Gerke, Colin McDiarmid. Graph imperfection II, J. Combinatorial Theory B (2001) 79-101
Stefanie Gerke, Colin McDiarmid. Graph imperfection, J. Combinatorial Theory B (2001) 58-78
Colin McDiarmid, Graph imperfection and channel assignment, J. Ramirez, B. Reed, editors Perfect Graphs, Wiley (2001) 215-231
Colin McDiarmid, Bruce Reed. Channel assignment on nearly bipartite and bounded treewidth graphs, Electronic Notes in Discrete Mathematics 10 (2001)
Malwina Luczak, Colin McDiarmid. Bisecting sparse planar graphs, Random Structures and Algorithms (2001) 31-38
2000
Colin McDiarmid, Bruce Reed. Channel assignment and weighted colouring, Networks (2000) 114-117
Colin McDiarmid. Frequency-distance constraints with large distances, Discrete Applied Mathematics 223 (2000) 227-251
1999
Chinh T. Hoang, Colin McDiarmid. A note on the divisibility of graphs, Congressus Numerantium 136 (1999) 215-219
Colin McDiarmid. Pattern minimisation in cutting stock problems, Discrete Mathematics 98 (1999) 121-130
Colin McDiarmid, Bruce Reed. Colouring proximity graphs in the plane, Discrete Mathematics, 199 (1999) 123-137
1998
Andrew Beveridge, Alan Frieze, Colin McDiarmid. Random minimum length spanning trees in regular graphs, Combinatorica 18 (1998) 311-333
Colin McDiarmid. Concentration. Probabilistic Methods for Algorithmic Discrete Mathematics, 1998, 1-46
1997
Alan Frieze, Colin McDiarmid. Algorithmic Theory of Random graphs, Random Structures and Algorithms, August 23 1996, 1-35
Colin McDiarmid. A doubly cyclic channel assignment problem, Discrete Applied Mathematics, 80 (1997) 263-268
Colin McDiarmid. Centering sequences with bounded differences
Colin McDiarmid. Probability
Colin McDiarmid. Hypergraph colouring and the Lovasz Local Lemma, Discrete Mathematics, 167/168 (1997) 481-486
Colin McDiarmid, Theodore Johnson, Harold S. Stone. On finding a minimum spanning tree in a network with random weights, Random Structures and Algorithms, Volume 10, Issue 1-2 (187-204) 1996
1996
Colin McDiarmid. A random bit-flipping method for seeking agreement, University of Oxford, 25 September 1995, 1-14
Noga Alon, Colin McDiarmid, Michael Molloy. Edge-disjoint cycles in regular directed graphs, Journal of Graph Theory, Vol 22, Issue 3 ( 231-237)
C.J.H. McDiarmid, R.B. Hayward. Large deviations for quicksort, Journal of Algorithms, 21, (1996) 476-507
Colin McDiarmid, Angelika Steger. Tidier examples for lower bounds on diagonal ramsey numbers, Journal of Combinatorial Theory, Series A 74, (1996) 147-152
1995
Robert Hochberg, Colin McDiarmid, Michael Saks. On the bandwidth of triangulated triangles, Discrete Mathematics, 138 261-265 (1995)
Colin McDiarmid, Minimal positions in a branching random walk, Annals of Applied Probability, Vol. 5, No. 1 (Feb. 1995) 128-139
Keith Edwards, Colin McDiarmid. The complexity of harmonious colouring for trees, Discrete Applied Mathematics, 57 (1995) 133-144
Colin McDiarmid, Bruce Reed. Almost every graph can be covered by [fracDelta2] linear forests, Combinatorics, Probability & Computing 4: 257-268 (1995)8 July 1994, 1-16
1994
C. McDiarmid, B. Reed, A. Schrijver, B. Shepherd. Induced circuits in planar graphs, Journal of Combinatorial Theory, Series B 60, (1994) 169-176
Colin J.H. McDiarmid, Jorge Ramirez Alfonsin. Sharing jugs of wine, Discrete Mathematics 125 (1994) 279-287
Keith Edwards, Colin McDiarmid. New upper bounds on harmonious colourings, J. Graph Theory, 18 (1994) 257-267
Colin J.H. McDiarmid, Abdon Sanchez-Arroyo. Total colouring regular bipartite graphs is NP-hard, Discrete Mathematics 124 (1994) 155-162
1993
Colin McDiarmid. A Random recolouring method for graphs and hypergraphs, Combinatorics, Probability and Computing, 2:363--365, 1993
Colin McDiarmid, Bruce Reed. On total colourings of graphs, Journal of Combinatorial Theory, Series B 57, 122-130 (1993)
Colin J.H. McDiarmid, Abdon Sanchez-Arroyo. An upper bound for total colouring of graphs, Discrete Mathematics 111 (1993) 389-392
1992
M.E. Dyer, Z. Furedi, C. McDiarmid. Volumes spanned by random points in the hypercube, Random Structures and Algorithms, Vol 3 Issue 1 , Pages 1 - 116 (1992)
Colin McDiarmid. On a correlation inequality of Farr, Combinatorics, Probability & Computing 1: 157-160 (1992)
W. Cook, M. Hartmann, R. Kannan, C. McDiarmid. On integer points in polyhedra, Combinatorica 12 (1), (1992) 27-37
Colin McDiarmid. Probability modelling and optimal location of a travelling salesman, Journal of the Operational Research Society, Vol. 43, No. 5, (May 1992) 533-538
Colin McDiarmid, Ryan Hayward. Strong concentration for quicksort, Proc. 3rd ACM-SIAM SODA (1992) 414-421
Noga Alon, Colin McDiarmid, Bruce Reed. Star arboricity, Combinatorica 12 (4) (1992) 375-380
V. Chvátal, C. McDiarmid. Small transversals in hypergraphs, Combinatorica 12 (1) (1992) 19-26
B. Reed, Colin McDiarmid. The strongly connected components of 1-in, 1-out, Combinatorics, Probability and Computing 1 (1992), 265-274
1991
Noga Alon, Colin McDiarmid, Bruce Reed. Acyclic colouring of graphs, Random Struct. Algorithms 2(3): 277-288 (1991)
C.J.H. McDiarmid, G.M.A. Provan. An expected-cost analysis of backtracking and non-backtracking algorithms, IJCAI 1991: 172-177
Colin McDiarmid, Luo Xinhua. Upper bounds for harmonious colourings, J. of Graph Theory, Vol. 18 Issue 2, Pages 205 - 209
Ryan Hayward, Colin McDiarmid. Average case analysis of heap building by repeated insertion, Journal of Algorithms 12, 126-153 (1991)
Colin McDiarmid. Expected numbers at hitting times, J. of Graph Theory, Vol. 15 Issue 6, Pages 637 - 648
Colin McDiarmid, Zevi Miller. Lattice bandwidth of random graphs, Discrete Applied Mathematics 30 (1991) 221-227
1990
Alan Frieze, Colin McDiarmid, Bruce Reed. Greedy matching on the line, SIAM J. COMPUT, 19, (1990), 666-672
A.M. Frieze, C.J.H. McDiarmid. On random minimum length spanning trees, Combinatorica 9 (4) (1989)
Colin McDiarmid. On the chromatic number of random graphs, Random Structures and Algorithms (1990) 435-442
Colin McDiarmid. Colourings of random graphs, R. Nelson, R.J. Wilson (editors), Pitman Research Notes in Mathematics Series 218, Longman Scientific 6 Technical 1990, 79-86
Colin McDiarmid, Bruce Reed. Linear arboricity of random regular graphs, Random Structures and Algorithms, 1 (1990), 443-445
M.E. Dyer, Z. Furedi, C. McDiarmid. Random volumes in the n-cube, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1, 1990, 33-38
C.J.H. McDiarmid. Probabilistic analysis of tree search,in G.Grimmett and D.J.A.Welsh eds., Disorder in Physical Systems, Oxford University Press, 1990, 249-260
1989
Colin McDiarmid. On the method of bounded differences, Surveys in Combinatorics, 1989, J. Siemons ed., London Mathematical Society Lecture Note Series 141, Cambridge University Press, 1989, 148-188
1985
Colin McDiarmid. On some conditioning results in the probabilistic analysis of algorithms, Discrete Applied Mathematics 10 (1985) 197-201
1979
Colin McDiarmid. Determining the chromatic number of a graph, SIAM J. Computing 8 (1979), 1-14
Printer Friendly Version 