Mike Molloy's papers

Back to my home page.

Here are several papers that I am making available online. These are not necessarily the final versions, just the latest .ps file that I have handy. The journal version will often have many errors corrected (and some still uncorrected). The copyright for each journal paper belongs to the publisher of that journal. Last updated Jan 13, 2005.

Graph Colouring:

• B. Farzad, M. Molloy and B. Reed. (Delta-k)-critical graphs. J. Comb. Th. (B), to appear.
• M. Molloy and M. Salavatipour. A bound on the chromatic number of the square of a planar graph.
• M. Molloy and B. Reed. Colouring graphs when the number of colours is almost the maximum degree. Proceedings of STOC 2001.
• A. Kundgen and M. Molloy. Multiplicities in Chromatic Degree Sequences. J. Graph th. 40, 68-74 (2002).
• M. Molloy and B. Reed. Near-Optimal List Colourings. Random Struc. & Alg. 17 , 376-402 (2000).
• M. Molloy. Chromatic Neighbourhoods. Journal of Graph Theory (31), 303-311 (1999).
• M. Molloy and B. Reed. A Bound on the Total Chromatic Number. Combinatorica 18 241-280 (1998).
• D. Achlioptas, J. Brown, D. Corneil and M. Molloy. The Existence of Uniquely -G Colourable Graphs. Discrete Math 179 1-11 (1998).
• H. Hind, M. Molloy and B. Reed. Total Colouring with Delta+poly(log Delta) Colours. SIAM Journal on Computing 28 816-821 (1998).
• H. Hind, M. Molloy and B. Reed. Colouring a Graph Frugally. Combinatorica 17 469-482 (1997).
• M. Molloy and B. Reed. A Bound on the Strong Chromatic Index of a Graph. Journal of Combinatorial Theory (B) 69 103-109 (1997).
• M. Molloy and B. Reed. Colouring Graphs whose Chromatic Number is Almost Their Maximum Degree. Latin American Theoretical Informatics, 1998.
• M. Molloy and B. Reed. Graph Colouring via the Probabilistic Method. Book chapter in "Graph Theory and Computational Biology", A. Gyrafas and L. Lovasz editors. pp. 125-155. J. Bolyai Math. Soc. 1999.

Random Graphs:

• M. Molloy. Cores in random hypergraphs and boolean formulas Random Structures and Algorithms (to appear). Conference version to appear in SODA 2004.
• M. Molloy and B. Reed. Critical Subgraphs of a Random Graph. Electronic J. Comb. 6 , R35 (1999).
• D. Achlioptas and M. Molloy. Almost All Graphs with 2.522 n Edges are not 3-Colourable. Electronic J. Comb. (6), R29 (1999).
• M. Molloy and B. Reed. The Size of the Largest Component of a Random Graph on a Fixed Degree Sequence. Combinatorics, Probability and Computing 7 , 295-306 (1998).
• M. Molloy, H. Robalewska, R. W. Robinson and N. C. Wormald. 1-Factorisations of Random Regular Graphs. Random Structures and Algorithms 10 305-321 (1997).
• C. Cooper, A. Frieze, M. Molloy, and B. Reed. Perfect Matchings in Random r-Regular, s-Uniform Hypergraphs. Combinatorics, Probability and Computing 5 1-14 (1996).
• A. Frieze, M. Jerrum, M. Molloy, R. W. Robinson and N. C. Wormald. Generating and Counting Hamilton Cycles in Random Regular Graphs. Journal of Algorithms. 21 176-198 (1996).
• M. Molloy. A Gap Between the Appearance of a k-Core and a (k+1)-Chromatic Graph. Random Structures and Algorithms 8 159-160 (1996).
• M. Molloy and B. Reed. A Critical Point for Random Graphs with a Given Degree Sequence. Random Structures and Algorithms 6 161-180 (1995).
• M. Molloy and B. Reed. The Dominating Number of a Random Cubic Graph. Random Structures and Algorithms 7 209-222 (1995).
• C. Cooper, A. Frieze and M. Molloy. Hamilton Cycles in Random Regular Digraphs. Combinatorics, Probability and Computing 3 39-50 (1994).
• A. Frieze and M. Molloy. Broadcasting in Random Graphs. Discrete Applied Math 54 77-79 (1994).
• D. Achlioptas and M. Molloy. Analysis of a List-colouring Algorithm on a Random Graph. FOCS 1997.
• A. Goerdt and M. Molloy. Analysis of edge deletion processes on random regular graphs. Latin American Theoretical Informatics, 2000. Journal version in Theoretical Computer Science (to appear).
• M. Molloy. Thresholds for colourability and satisfiability for random graphs and boolean formulae. Book chapter in "Surveys in Combinatorics", J. Hirschfield, ed., Cambridge University Press, 2001.

Random Boolean Formulas and Constraint Satisfaction Problems:

• H. Hatami and M. Molloy. Sharp thresholds for constraint satisfaction problems and homomorphisms (submitted).
• M. Molloy. When does the giant component bring unsatisfiability? Combinatorica (to appear).
• D. Achlioptas, P. Beame and M. Molloy, Exponential bounds for DPLL below the satisfiability threshold. in Proceedings of SODA 2004.
• D. Achlioptas, L. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, and Y. Stamatiou. Random Constraint Satisfaction: A More Accurate Picture. Constraints 6, 329~-~344 (2001).
• D. Achlioptas, P. Beame and M. Molloy, A sharp threshold in proof complexity. Journal of Computer and System Sciences (to appear). Conference version in Proceedings of STOC 2001.
• M. Molloy. Models for Random Constraint Satisfaction Problems. Conference version in Proceedings of STOC 2002.
• M. Dyer, A. Frieze and M. Molloy. A probabilistic analysis of randomly generated binary constraint satisfaction problems.
• A. Frieze and M. Molloy. The satisfiability threshold for randomly generated binary constraint satisfaction problems. (Submitted). Conference version appeared in Proceedings of RANDOM 2003. A correction to the references in the conference version.
• M. Molloy and M. Salavatipour. The resolution complexity of random constraint satisfaction problems. (preprint). Conference version to appear in Proceedings of FOCS 2003.

Rapidly Mixing Markov Chains

• D. Achlioptas, M. Molloy, C. Moore and F. Van Bussel. Sampling grid colourings with fewer colours. Proceedings of LATIN 2004.
• M. Dyer, C. Greenhill and M. Molloy. Very rapid mixing of the Glauber dynamics for proper colourings on bounded-degree graphs. Random Struc. & Alg. 20, 98-114 (2002).
• M. Molloy. Very rapidly mixing Markov Chains for (2 Delta)-colourings and for independent sets in a 4-regular graph. Random Struc. & Alg. 18 , 101-115 (2001).
• M. Molloy. The Glauber dynamics on the colourings of a graph with large girth and maximum degree. SIAM J. Computing (to appear).Conference version in Proceedings of STOC 2002.
• M. Molloy, B. Reed and W. Steiger. On the Mixing Rate of the Triangulation walk. Proceedings of the 1997 DIMACS Workshop on Randomization Methods in Algorithm Design, 179-190.

Miscellaneous

• N. Alon, P. Erdos, D. Gunderson and M. Molloy. On a Ramsey-type Problem. J. Graph Th. 40, 120-129 (2002).
• M. Molloy and L. Sedgwick. Isomorphism certificates for undirected graphs. Discrete Math. (to appear)
• A. Frieze and M. Molloy. Splitting an Expander Graph. Journal of Algorithms (to appear).
• N. Alon, C. McDiarmid and M. Molloy. Edge-Disjoint Cycles in Regular Directed Graphs. Journal of Graph Theory 22 231-237 (1996).
• R. Grenier, R, Hayward and M. Molloy. Optimal depth-first strategies for and-or trees. Conference version in AAAI 2002.
• M. Molloy and B. Reed. Further Algorithmic Aspects of the Lovasz Local Lemma. Proceedings of STOC 1998, 524-529.
• M. Molloy. The Probabilistic Method. Book chapter in "Probabilistic Methods for Algorithmic Discrete Mathematics", M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed, editors. pp. 1-35. Springer, 1998.