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.
Mike Molloy
Department of Computer Science
University of Toronto
(416) 978-1932
molloy@cs.toronto.edu