Michael Molloy

Orcid: 0000-0001-5435-1015

Affiliations:
  • University of Toronto, Canada


According to our database1, Michael Molloy authored at least 87 papers between 1994 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Adaptable and conflict colouring multigraphs with no cycles of length three or four.
J. Graph Theory, September, 2023

A variant of the Erdős-Rényi random graph process.
J. Graph Theory, 2023

2022
Asymptotically good edge correspondence colourings.
J. Graph Theory, 2022

Fractional Cocoloring of Graphs.
Graphs Comb., 2022

The degree-restricted random process is far from uniform.
CoRR, 2022

2020
<i>k</i>-regular subgraphs near the <i>k</i>-core threshold of a random graph.
J. Comb. Theory B, 2020

2019
The list chromatic number of graphs with small clique number.
J. Comb. Theory B, 2019

2018
The stripping process can be slow: Part I.
Random Struct. Algorithms, 2018

Inside the clustering window for random linear equations.
Random Struct. Algorithms, 2018

The Freezing Threshold for <i>k</i>-Colourings of a Random Graph.
J. ACM, 2018

2017
The Adaptable Chromatic Number and the Chromatic Number.
J. Graph Theory, 2017

Space proof complexity for random 3-CNFs.
Inf. Comput., 2017

A Note on the Rainbow Connection of Random Regular Graphs.
Electron. J. Comb., 2017

2016
Backbone colourings of graphs.
Discret. Math., 2016

2015
The solution space geometry of random linear equations.
Random Struct. Algorithms, 2015

2014
Sets that are connected in two random graphs.
Random Struct. Algorithms, 2014

Colouring graphs when the number of colours is almost the maximum degree.
J. Comb. Theory B, 2014

2013
A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems.
SIAM J. Comput., 2013

Containing Viral Spread on Sparse Random Graphs: Bounds, Algorithms, and Experiments.
Internet Math., 2013

Inside the clustering threshold for random linear equations.
CoRR, 2013

Frozen variables in random boolean constraint satisfaction problems.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem.
SIAM J. Discret. Math., 2012

The scaling window for a random graph with a given degree sequence.
Random Struct. Algorithms, 2012

An asymptotically tight bound on the adaptable chromatic number.
J. Graph Theory, 2012

(<i>k</i>+1)-Cores Have <i>k</i>-Factors.
Comb. Probab. Comput., 2012

The freezing threshold for k-colourings of a random graph.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011
The Glauber Dynamics for Colorings of Bounded Degree Trees.
SIAM J. Discret. Math., 2011

The adaptable choosability number grows with the choosability number.
Discret. Math., 2011

2010
Corrigendum to "Asymptotically optimal frugal colouring" [J. Combin. Theory Ser. B 100 (2) (2010) 226-246].
J. Comb. Theory B, 2010

Asymptotically optimal frugal colouring.
J. Comb. Theory B, 2010

2009
On the edge-density of 4-critical graphs.
Comb., 2009

The Glauber Dynamics for Colourings of Bounded Degree Trees.
Proceedings of the Approximation, 2009

2008
Sharp thresholds for constraint satisfaction problems and homomorphisms.
Random Struct. Algorithms, 2008

When does the giant component bring unsatisfiability?
Comb., 2008

2007
The Resolution Complexity of Random Constraint Satisfaction Problems.
SIAM J. Comput., 2007

2006
The satisfiability threshold for randomly generated binary constraint satisfaction problems.
Random Struct. Algorithms, 2006

Finding optimal satisficing strategies for and-or trees.
Artif. Intell., 2006

Randomly Colouring Graphs with Girth Five and Large Maximum Degree.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005
Cores in random hypergraphs and Boolean formulas.
Random Struct. Algorithms, 2005

A bound on the chromatic number of the square of a planar graph.
J. Comb. Theory B, 2005

(<i>Delta-k</i>)-critical graphs.
J. Comb. Theory B, 2005

2004
The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree.
SIAM J. Comput., 2004

A sharp threshold in proof complexity yields lower bounds for satisfiability search.
J. Comput. Syst. Sci., 2004

The pure literal rule threshold and cores in random hypergraphs.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Exponential bounds for DPLL below the satisfiability threshold.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Sampling Grid Colorings with Fewer Colors.
Proceedings of the LATIN 2004: Theoretical Informatics, 2004

The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Analysis of edge deletion processes on faulty random regular graphs.
Theor. Comput. Sci., 2003

A probabilistic analysis of randomly generated binary constraint satisfaction problems.
Theor. Comput. Sci., 2003

Models for Random Constraint Satisfaction Problems.
SIAM J. Comput., 2003

2002
Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs.
Random Struct. Algorithms, 2002

Extremal problems for chromatic neighborhood sets.
J. Graph Theory, 2002

A Ramsey-type problem and the Turán numbers.
J. Graph Theory, 2002

Isomorphism certificates for undirected graphs.
Discret. Math., 2002

Models and thresholds for random constraint satisfaction problems.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

The Glauber dynamics on colourings of a graph with high girth and maximum degree.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Frequency Channel Assignment on Planar Networks.
Proceedings of the Algorithms, 2002

Optimal Depth-First Strategies for And-Or Trees.
Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28, 2002

2001
Very rapidly mixing Markov chains for 2-colorings and for independent sets in a graph with maximum degree 4.
Random Struct. Algorithms, 2001

Random Constraint Satisfaction: A More Accurate Picture.
Constraints An Int. J., 2001

Colouring graphs when the number of colours is nearly the maximum degree.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A sharp threshold in proof complexity.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000
Near-optimal list colorings.
Random Struct. Algorithms, 2000

k-Colouring when k is close to Delta.
Electron. Notes Discret. Math., 2000

1999
Chromatic neighborhood sets.
J. Graph Theory, 1999

Splitting an Expander Graph.
J. Algorithms, 1999

Critical Subgraphs of a Random Graph.
Electron. J. Comb., 1999

Almost all graphs with 2.522 n edges are not 3-colorable.
Electron. J. Comb., 1999

1998
Total Coloring With Delta + (log Delta) Colors.
SIAM J. Comput., 1998

The existence of uniquely -G colourable graphs.
Discret. Math., 1998

The Size of the Giant Component of a Random Graph with a Given Degree Sequence.
Comb. Probab. Comput., 1998

A Bound on the Total Chromatic Number.
Comb., 1998

Further Algorithmic Aspects of the Local Lemma.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree.
Proceedings of the LATIN '98: Theoretical Informatics, 1998

1997
1-Factorizations of random regular graphs.
Random Struct. Algorithms, 1997

A Bound on the Strong Chromatic Index of a Graph<sup>, </sup>.
J. Comb. Theory B, 1997

Colouring a Graph Frugally.
Comb., 1997

The Analysis of a List-Coloring Algorithm on a Random Graph.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

On the mixing rate of the triangulation walk.
Proceedings of the Randomization Methods in Algorithm Design, 1997

1996
A gap between the appearances of a k-core and a (k+1)-chromatic graph.
Random Struct. Algorithms, 1996

Edge-disjoint cycles in regular directed graphs.
J. Graph Theory, 1996

Generating and Counting Hamilton Cycles in Random Regular Graphs.
J. Algorithms, 1996

Perfect Matchings in Random r-regular, s-uniform Hypergraphs.
Comb. Probab. Comput., 1996

1995
A Critical Point for Random Graphs with a Given Degree Sequence.
Random Struct. Algorithms, 1995

The Dominating Number of Random Cubic Graph.
Random Struct. Algorithms, 1995

1994
Broadcasting in Random Graphs.
Discret. Appl. Math., 1994

Hamilton Cycles in Random Regular Digraphs.
Comb. Probab. Comput., 1994


  Loading...