Michael Molloy

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

Collaborative distances:

• Dijkstra number of three.
• Erdős number of one.

2023

Adaptable and conflict colouring multigraphs with no cycles of length three or four.

Jurgen Aliaj, Michael Molloy

J. Graph Theory, September, 2023

A variant of the Erdős-Rényi random graph process.

Adam Logan, Michael Molloy, Pawel Pralat

J. Graph Theory, 2023

2022

Asymptotically good edge correspondence colourings.

Michael Molloy, Luke Postle

J. Graph Theory, 2022

Fractional Cocoloring of Graphs.

John Gimbel, André Kündgen, Michael Molloy

Graphs Comb., 2022

The degree-restricted random process is far from uniform.

Michael Molloy, Erlang Surya, Lutz Warnke

CoRR, 2022

2020

<i>k</i>-regular subgraphs near the <i>k</i>-core threshold of a random graph.

Dieter Mitsche, Michael Molloy, Pawel Pralat

J. Comb. Theory, Ser. B, 2020

2019

The list chromatic number of graphs with small clique number.

Michael Molloy

J. Comb. Theory, Ser. B, 2019

2018

The stripping process can be slow: Part I.

Pu Gao, Michael Molloy

Random Struct. Algorithms, 2018

Inside the clustering window for random linear equations.

Pu Gao, Michael Molloy

Random Struct. Algorithms, 2018

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

Michael Molloy

J. ACM, 2018

2017

The Adaptable Chromatic Number and the Chromatic Number.

Michael Molloy

J. Graph Theory, 2017

Space proof complexity for random 3-CNFs.

Patrick Bennett, Ilario Bonacina, Nicola Galesi, Tony Huynh, Mike Molloy, Paul Wollan

Inf. Comput., 2017

A Note on the Rainbow Connection of Random Regular Graphs.

Michael Molloy

Electron. J. Comb., 2017

2016

Backbone colourings of graphs.

Babak Farzad, Arnoosh Golestanian, Michael Molloy

Discret. Math., 2016

2015

The solution space geometry of random linear equations.

Dimitris Achlioptas, Michael Molloy

Random Struct. Algorithms, 2015

2014

Sets that are connected in two random graphs.

Michael Molloy

Random Struct. Algorithms, 2014

Colouring graphs when the number of colours is almost the maximum degree.

Michael Molloy, Bruce A. Reed

J. Comb. Theory, Ser. B, 2014

2013

A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems.

Siu On Chan, Michael Molloy

SIAM J. Comput., 2013

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

Milan Bradonjic, Michael Molloy, Guanhua Yan

Internet Math., 2013

Inside the clustering threshold for random linear equations.

Pu Gao, Michael Molloy

CoRR, 2013

Frozen variables in random boolean constraint satisfaction problems.

Michael Molloy, Ricardo Restrepo

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.

Harold S. Connamacher, Michael Molloy

SIAM J. Discret. Math., 2012

The scaling window for a random graph with a given degree sequence.

Hamed Hatami, Michael Molloy

Random Struct. Algorithms, 2012

An asymptotically tight bound on the adaptable chromatic number.

Michael Molloy, Giovanna Thron

J. Graph Theory, 2012

(<i>k</i>+1)-Cores Have <i>k</i>-Factors.

Siu On Chan, Michael Molloy

Comb. Probab. Comput., 2012

The freezing threshold for k-colourings of a random graph.

Michael Molloy

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

The Glauber Dynamics for Colorings of Bounded Degree Trees.

Brendan Lucier, Michael Molloy

SIAM J. Discret. Math., 2011

The adaptable choosability number grows with the choosability number.

Michael Molloy, Giovanna Thron

Discret. Math., 2011

2010

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

Michael Molloy, Bruce A. Reed

J. Comb. Theory, Ser. B, 2010

Asymptotically optimal frugal colouring.

Michael Molloy, Bruce A. Reed

J. Comb. Theory, Ser. B, 2010

2009

On the edge-density of 4-critical graphs.

Babak Farzad, Michael Molloy

Comb., 2009

The Glauber Dynamics for Colourings of Bounded Degree Trees.

Brendan Lucier, Michael Molloy, Yuval Peres

Proceedings of the Approximation, 2009

2008

Sharp thresholds for constraint satisfaction problems and homomorphisms.

Hamed Hatami, Michael Molloy

Random Struct. Algorithms, 2008

When does the giant component bring unsatisfiability?

Michael Molloy

Comb., 2008

2007

The Resolution Complexity of Random Constraint Satisfaction Problems.

Michael Molloy, Mohammad R. Salavatipour

SIAM J. Comput., 2007

2006

The satisfiability threshold for randomly generated binary constraint satisfaction problems.

Alan M. Frieze, Michael Molloy

Random Struct. Algorithms, 2006

Finding optimal satisficing strategies for and-or trees.

Russell Greiner, Ryan Hayward, Magdalena Jankowska, Michael Molloy

Artif. Intell., 2006

Randomly Colouring Graphs with Girth Five and Large Maximum Degree.

Lap Chi Lau, Michael Molloy

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005

Cores in random hypergraphs and Boolean formulas.

Michael Molloy

Random Struct. Algorithms, 2005

A bound on the chromatic number of the square of a planar graph.

Michael Molloy, Mohammad R. Salavatipour

J. Comb. Theory, Ser. B, 2005

(<i>Delta-k</i>)-critical graphs.

Babak Farzad, Michael S. O. Molloy, Bruce A. Reed

J. Comb. Theory, Ser. B, 2005

2004

The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree.

Michael Molloy

SIAM J. Comput., 2004

A sharp threshold in proof complexity yields lower bounds for satisfiability search.

Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy

J. Comput. Syst. Sci., 2004

The pure literal rule threshold and cores in random hypergraphs.

Michael Molloy

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Exponential bounds for DPLL below the satisfiability threshold.

Dimitris Achlioptas, Paul Beame, Michael Molloy

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Sampling Grid Colorings with Fewer Colors.

Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore, Frank Van Bussel

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem.

Harold S. Connamacher, Michael Molloy

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Analysis of edge deletion processes on faulty random regular graphs.

Andreas Goerdt, Michael Molloy

Theor. Comput. Sci., 2003

A probabilistic analysis of randomly generated binary constraint satisfaction problems.

Martin E. Dyer, Alan M. Frieze, Michael Molloy

Theor. Comput. Sci., 2003

Models for Random Constraint Satisfaction Problems.

Michael Molloy

SIAM J. Comput., 2003

2002

Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs.

Martin E. Dyer, Catherine S. Greenhill, Michael Molloy

Random Struct. Algorithms, 2002

Extremal problems for chromatic neighborhood sets.

André Kündgen, Michael Molloy

J. Graph Theory, 2002

A Ramsey-type problem and the Turán numbers.

Noga Alon, Paul Erdös, David S. Gunderson, Michael Molloy

J. Graph Theory, 2002

Isomorphism certificates for undirected graphs.

Michael Molloy, Laura Sedgwick

Discret. Math., 2002

Models and thresholds for random constraint satisfaction problems.

Michael Molloy

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.

Michael Molloy

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Frequency Channel Assignment on Planar Networks.

Michael Molloy, Mohammad R. Salavatipour

Proceedings of the Algorithms, 2002

Optimal Depth-First Strategies for And-Or Trees.

Russell Greiner, Ryan Hayward, Michael Molloy

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.

Michael Molloy

Random Struct. Algorithms, 2001

Random Constraint Satisfaction: A More Accurate Picture.

Dimitris Achlioptas, Michael S. O. Molloy, Lefteris M. Kirousis, Yannis C. Stamatiou, Evangelos Kranakis, Danny Krizanc

Constraints An Int. J., 2001

Colouring graphs when the number of colours is nearly the maximum degree.

Michael Molloy, Bruce A. Reed

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A sharp threshold in proof complexity.

Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Near-optimal list colorings.

Michael Molloy, Bruce A. Reed

Random Struct. Algorithms, 2000

k-Colouring when k is close to Delta.

Michael Molloy, Bruce A. Reed

Electron. Notes Discret. Math., 2000

1999

Chromatic neighborhood sets.

Michael Molloy

J. Graph Theory, 1999

Splitting an Expander Graph.

Alan M. Frieze, Michael Molloy

J. Algorithms, 1999

Critical Subgraphs of a Random Graph.

Michael Molloy, Bruce A. Reed

Electron. J. Comb., 1999

Almost all graphs with 2.522 n edges are not 3-colorable.

Dimitris Achlioptas, Michael Molloy

Electron. J. Comb., 1999

1998

Total Coloring With Delta + (log Delta) Colors.

Hugh Hind, Michael Molloy, Bruce A. Reed

SIAM J. Comput., 1998

The existence of uniquely -G colourable graphs.

Dimitris Achlioptas, Jason I. Brown, Derek G. Corneil, Michael Molloy

Discret. Math., 1998

The Size of the Giant Component of a Random Graph with a Given Degree Sequence.

Michael Molloy, Bruce A. Reed

Comb. Probab. Comput., 1998

A Bound on the Total Chromatic Number.

Michael Molloy, Bruce A. Reed

Comb., 1998

Further Algorithmic Aspects of the Local Lemma.

Michael Molloy, Bruce A. Reed

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree.

Michael Molloy, Bruce A. Reed

Proceedings of the LATIN '98: Theoretical Informatics, 1998

1997

1-Factorizations of random regular graphs.

Michael Molloy, Hanna D. Robalewska, Robert W. Robinson, Nicholas C. Wormald

Random Struct. Algorithms, 1997

A Bound on the Strong Chromatic Index of a Graph^,.

Michael Molloy, Bruce A. Reed

J. Comb. Theory, Ser. B, 1997

Colouring a Graph Frugally.

Hugh Hind, Michael Molloy, Bruce A. Reed

Comb., 1997

The Analysis of a List-Coloring Algorithm on a Random Graph.

Dimitris Achlioptas, Michael S. O. Molloy

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

On the mixing rate of the triangulation walk.

Michael S. O. Molloy, Bruce A. Reed, William Steiger

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.

Michael Molloy

Random Struct. Algorithms, 1996

Edge-disjoint cycles in regular directed graphs.

Noga Alon, Colin McDiarmid, Michael Molloy

J. Graph Theory, 1996

Generating and Counting Hamilton Cycles in Random Regular Graphs.

Alan M. Frieze, Mark Jerrum, Michael Molloy, Robert W. Robinson, Nicholas C. Wormald

J. Algorithms, 1996

Perfect Matchings in Random r-regular, s-uniform Hypergraphs.

Colin Cooper, Alan M. Frieze, Michael Molloy, Bruce A. Reed

Comb. Probab. Comput., 1996

1995

A Critical Point for Random Graphs with a Given Degree Sequence.

Michael Molloy, Bruce A. Reed

Random Struct. Algorithms, 1995

The Dominating Number of Random Cubic Graph.

Michael Molloy, Bruce A. Reed

Random Struct. Algorithms, 1995

1994

Broadcasting in Random Graphs.

Alan M. Frieze, Michael Molloy

Discret. Appl. Math., 1994

Hamilton Cycles in Random Regular Digraphs.

Colin Cooper, Alan M. Frieze, Michael Molloy

Comb. Probab. Comput., 1994