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 Nov 2022.
Graph
Colouring:
- J. Aliaj and M.
Molloy Adaptable and conflict colouring multigraphs with no
cycles of length three and four. arXiv: 2107.04253
- M. Molloy and L.
Postle. Asymptotically
good edge correspondence colouring. Journal of
Graph Theory 100, 559-577 (2022).
- J. Gimble,
A. Kundgen and M. Molloy. Fractional co-coloring of
graphs. Graphs and Combinatorics 38 (2022).
- M. Molloy.
The list chromatic
number of graphs with small clique number. J. Comb.
Th.(B) 134, 264-284 (2019).
- M. Molloy.
The adaptable chromatic number and the
chromatic number. Journal of
Graph Theory 84, 53-56 (2017).
- B. Farzad,
A. Golestanian, M. Molloy. Backbone
colourings of graphs. Discrete Math., 339,
2721-2722 (2016).
- M. Molloy
and G. Thron. An asymptotically tight
bound on the adaptable chromatic number. Journal of
Graph Theory 71, 331-351 (2012).
- M. Molloy
and G. Thron. The adaptable choosability
number grows with the choosability
number. Discrete Math 311, 2268-2271 (2011).
- M. Molloy
and B. Reed. Colouring graphs when the
number of colours is almost the maximum degree. J. Comb.
Th.(B) 109, 134-195 (2014).
- M. Molloy
and B. Reed. Asymptotically optimal
frugal colouring. J.
Comb. Th. (B) 100, 226-246 (2010).
Conference version in proceedings of SODA 2009.
- B. Farzad and M. Molloy. On the edge-density of 4-critical
graphs. Combinatorica 29,
665-689 (2009).
- 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:
- M. Molloy, E. Surya and L.
Warnke. The degree-restricted random graph process is far from
uniform. arXiv: 2211.00835
- A. Logan, M. Molloy, P. Pralat. A variant of the
Erdos-Renyi random graph process. J. Gr Th. (to
appear).
- D. Mitsche, M. Molloy, P.
Pralat. k-regular
subgraphs near the k-core threshold of a random graph.
J. Comb. Th. (B) 142, 106-143 (2020)
- P. Gao and M. Molloy. The stripping
process can be slow: part I. Rand. Struc. & Alg. 53,
76-139 (2018
- M. Molloy. The
rainbow connection number for random 3-regular graphs.
Elec. J. Comb. 24 P3.49 (2017).
- M. Molloy. Sets
that are connected in two random graphs. Random
Struc. & Alg. 45, 498-512 (2014).
- M Bradonjić, M Molloy and G Yan.
Containing Viral
Spread on Sparse Random Graphs: Bounds, Algorithms, and
Experiments.
Internet Mathematics 9, 406-433 (2013).
- H. Hatami and M. Molloy. The scaling window for a random
graph with a given degree sequence. Random Struc.
& Alg. 41, 99-123 (2012). Conference
version in proceedings of SODA 2010.
- S. Chan
and M. Molloy. (k+1)-cores have
k-factors. Combinatorics, Probability and
Computing 21, 882-896 (2012).
- 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:
- P. Bennett, I. Bonacina, N. Galesi, T. Huynh, M. Molloy and
P. Wollan. Space
proof complexity for random 3-CNFs. Info. &
Comp. 255, 165-176 (2017).
- P. Gao and M. Molloy. Inside the
clustering threshold for random linear equations.
Rand. Struc. & Alg. 52, 197-218 (2018).
- M. Molloy and R. Restrepo. Frozen variables in random
constraint satisfaction problems. SODA 2013
- M. Molloy. The freezing
threshold for k-colourings of a random graph.
J.ACM 65, Vol. 2, Art. 7 (2018). Conference
version in STOC 2012
- D. Achlioptas and M. Molloy. The
solution space geometry of random linear equations.
Random Structures and Algorithms 46, 197-231 (2015). Arxiv.
- H. Connamacher and M. Molloy. The satisfiability
threshold for a seemingly intractable random constraint
satisfaction problem. SIAM J. Disc. Math. 26,
145-168 (2012). Conference version in Proceedings of
FOCS 2004.
- S. Chan and M. Molloy. A dichotomy
theorem for the resolution complexity of random constraint
satisfaction problems. SIAM J. Computing
42, 27-60 (2013). Conference
version in 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. SIAM
J. Disc. Math 25, 827-853 (2011).
- B. Lucier, M. Molloy and Y. Peres. The Glauber
dynamics for colourings of bounded degree trees. Proceedings of
RANDOM 2009. 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