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 surfacesJ. Combinatorial Theory B 98 (2008) 778-797.

Colin McDiarmid and Bruce Reed, On the maximum degree of a random planar graph, Combinatorics, Probability and Computing17 (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 graphsEuroComb 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 colouringsJ. 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. COMPUT19, (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 graphSIAM J. Computing 8 (1979), 1-14

 

Back to top

Home