# Michael Molloy

According to our database

Collaborative distances:

^{1}, Michael Molloy authored at least 80 papers between 1994 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2019

The list chromatic number of graphs with small clique number.

J. Comb. Theory, Ser. 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

*k*-Colourings of a Random Graph.
J. ACM, 2018

2017

The Adaptable Chromatic Number and the Chromatic Number.

Journal of Graph Theory, 2017

A Note on the Rainbow Connection of Random Regular Graphs.

Electr. J. Comb., 2017

2016

Backbone colourings of graphs.

Discrete Mathematics, 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, Ser. B, 2014

2013

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

Internet Mathematics, 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. Discrete Math., 2012

An asymptotically tight bound on the adaptable chromatic number.

Journal of Graph Theory, 2012

Combinatorics, Probability & Computing, 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. Discrete Math., 2011

The adaptable choosability number grows with the choosability number.

Discrete Mathematics, 2011

2010

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

J. Comb. Theory, Ser. B, 2010

The Scaling Window for a Random Graph with a Given Degree Sequence.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

On the edge-density of 4-critical graphs.

Combinatorica, 2009

Asymptotically optimal frugal colouring.

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 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?

Combinatorica, 2008

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

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

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, Ser. B, 2005

(

*Delta-k*)-critical graphs.
J. Comb. Theory, Ser. 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

A probabilistic analysis of randomly generated binary constraint satisfaction problems.

Theor. Comput. Sci., 2003

Models for Random Constraint Satisfaction Problems.

SIAM J. Comput., 2003

The Satisfiability Threshold for Randomly Generated Binary Constraint Satisfaction Problems.

Proceedings of the Approximation, 2003

The Resolution Complexity of Random Constraint Satisfaction Problems.

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 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.

Journal of Graph Theory, 2002

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

Journal of Graph Theory, 2002

Isomorphism certificates for undirected graphs.

Discrete Mathematics, 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, 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.

Electronic Notes in Discrete Mathematics, 2000

Analysis of Edge Deletion Processes on Faulty Random Regular Graphs.

Proceedings of the LATIN 2000: Theoretical Informatics, 2000

1999

Chromatic neighborhood sets.

Journal of Graph Theory, 1999

Splitting an Expander Graph.

J. Algorithms, 1999

Critical Subgraphs of a Random Graph.

Electr. J. Comb., 1999

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

Electr. J. Comb., 1999

1998

Total Coloring With Delta + (log Delta) Colors.

SIAM J. Comput., 1998

The existence of uniquely -G colourable graphs.

Discrete Mathematics, 1998

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

Combinatorics, Probability & Computing, 1998

A Bound on the Total Chromatic Number.

Combinatorica, 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

^{, }.
J. Comb. Theory, Ser. B, 1997

Colouring a Graph Frugally.

Combinatorica, 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

Random Constraint Satisfaction: A More Accurate Picture.

Proceedings of the Principles and Practice of Constraint Programming - CP97, Third International Conference, Linz, Austria, October 29, 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.

Journal of Graph Theory, 1996

Generating and Counting Hamilton Cycles in Random Regular Graphs.

J. Algorithms, 1996

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

Combinatorics, Probability & Computing, 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.

Discrete Applied Mathematics, 1994

Hamilton Cycles in Random Regular Digraphs.

Combinatorics, Probability & Computing, 1994