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 July 2009.

Graph Colouring:

• M. Molloy and B. Reed. Colouring graphs when the number of colours is almost the maximum degree. Submitted.
• M. Molloy and B. Reed. Asymptotically optimal frugal colouring. JCT(B) (to appear). Conference version in proceedings of SODA 2009.
• B. Farzad and M. Molloy. On the edge-density of 4-critical graphs. Combinatorica, to appear.
• B. Farzad, M. Molloy and B. Reed. (Delta-k)-critical graphs. J. Comb. Th. (B) (93), 173-185 (2005).
• M. Molloy and M. Salavatipour. A bound on the chromatic number of the square of a planar graph. J. Comb. Th. (B) (94), 189-213 (2005)
• 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. Extremal Problems for Chromatic Neighbourhood Sets. 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 Neighbourhood Sets. 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:

• H. Hatami and M. Molloy. The scaling window for a random graph with a given degree sequence. Submitted.
• S. Chan and M. Molloy. (k+1)-cores have k-factors. Submitted.
• M. Molloy. Cores in random hypergraphs and boolean formulas Random Structures and Algorithms (27), 124-135 (2005). Conference version in SODA 2004.
• 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 (297), 241-260 (2003).
• 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.
• 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).
• D. Achlioptas and M. Molloy. Analysis of a List-colouring Algorithm on a Random Graph. FOCS 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).

Random Boolean Formulas and Constraint Satisfaction Problems:

• S. Chan and M. Molloy. A dichotomy theorem for the resolution complexity of random constraint satisfaction problems. FOCS 2008.
• H. Hatami and M. Molloy. Sharp thresholds for constraint satisfaction problems and homomorphisms. Random Structures and Algorithms 33 310-332 (2008).
• M. Molloy. When does the giant component bring unsatisfiability? Combinatorica 28 693-734 (2008).
• D. Achlioptas, P. Beame and M. Molloy, Exponential bounds for DPLL below the satisfiability threshold. in Proceedings of SODA 2004.
• M. Molloy and M. Salavatipour. The resolution complexity of random constraint satisfaction problems. SIAM J. Comp. (37), 895 - 922 (2007). Conference version in Proceedings of FOCS 2003.
• A. Frieze and M. Molloy. The satisfiability threshold for randomly generated binary constraint satisfaction problems. Random Structures and Algorithms (28), 323-339 (2006). Conference version appeared in Proceedings of RANDOM 2003. A correction to the references in the conference version.
• M. Dyer, A. Frieze and M. Molloy. A probabilistic analysis of randomly generated binary constraint satisfaction problems.
Theoretical Computer Science (290), 1815-1828 (2003).
• M. Molloy. Models for Random Constraint Satisfaction Problems. Conference version in Proceedings of STOC 2002.
• D. Achlioptas, P. Beame and M. Molloy, A sharp threshold in proof complexity. Journal of Computer and System Sciences (68), 238-268 (2004). Conference version in Proceedings of STOC 2001.
• 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).

Rapidly Mixing Markov Chains

• B. Lucier and M. Molloy. The Glauber dynamics for colourings of bounded degree trees. Submitted.
• B. Lucier, M. Molloy and Y. Peres. The Glauber dynamics for colourings of bounded degree trees. Submitted. This is a conference submission containing the results of the paper above, along with a strengthened main theorem.
• L. Lau and M. Molloy. Randomly colouring graphs with girth five and large maximum degree. Proceedings of LATIN 2006.
• D. Achlioptas, M. Molloy, C. Moore and F. Van Bussel. Rapid Mixing for Lattice Colourings with Fewer Colours J. Stat. Mech.: Theory and Experiment, 2005, P10012. Conference version in 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. The Glauber dynamics on the colourings of a graph with large girth and maximum degree. SIAM J. Computing (33) 721-737 (2004).Conference version in Proceedings of STOC 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, 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. (256), 349-359 (2002)
• A. Frieze and M. Molloy. Splitting an Expander Graph. Journal of Algorithms (33), 166-172 (1999).
• 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, M. Jankowska and M. Molloy. Finding Optimal Satisficing Solutions for And-Or Trees. Artificial Intelligence (170), 19-58 (2006). 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.