# Michael Krivelevich

According to our database1, Michael Krivelevich authored at least 185 papers between 1994 and 2018.

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

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2018
Finding and Using Expanders in Locally Sparse Graphs.
SIAM J. Discrete Math., 2018

The random k-matching-free process.
Random Struct. Algorithms, 2018

On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments.
Random Struct. Algorithms, 2018

Clique coloring of dense random graphs.
Journal of Graph Theory, 2018

Proper colouring Painter-Builder game.
Discrete Mathematics, 2018

Packing Hamilton Cycles Online.
Combinatorics, Probability & Computing, 2018

The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property.
Proceedings of the 29th International Conference on Probabilistic, 2018

2017
Bounded-Degree Spanning Trees in Randomly Perturbed Graphs.
SIAM J. Discrete Math., 2017

Finding paths in sparse random graphs requires many queries.
Random Struct. Algorithms, 2017

Efficient Winning Strategies in Random-Turn Maker-Breaker Games.
Journal of Graph Theory, 2017

Counting and packing Hamilton cycles in dense graphs and oriented graphs.
J. Comb. Theory, Ser. B, 2017

Waiter-Client and Client-Waiter Hamiltonicity games on random graphs.
Eur. J. Comb., 2017

Small Subgraphs in the Trace of a Random Walk.
Electr. J. Comb., 2017

Compatible Hamilton cycles in Dirac graphs.
Combinatorica, 2017

2016
Compatible Hamilton cycles in random graphs.
Random Struct. Algorithms, 2016

Finding Hamilton cycles in random graphs with few queries.
Random Struct. Algorithms, 2016

Some Remarks on Rainbow Connectivity.
Journal of Graph Theory, 2016

Editorial.
J. Comb. Theory, Ser. B, 2016

On saturation games.
Eur. J. Comb., 2016

Waiter-Client and Client-Waiter planarity, colorability and minor games.
Discrete Mathematics, 2016

Cycles and Matchings in Randomly Perturbed Digraphs and Hypergraphs.
Combinatorics, Probability & Computing, 2016

Manipulative Waiters with Probabilistic Intuition.
Combinatorics, Probability & Computing, 2016

The Phase Transition in Site Percolation on Pseudo-Random Graphs.
Electr. J. Comb., 2016

Client-Waiter Games on Complete and Random Graphs.
Electr. J. Comb., 2016

Random Graphs, Geometry and Asymptotic Structure.
London Mathematical Society student texts 84, Cambridge University Press, ISBN: 978-1-316-50191-7, 2016

2015
Large Subgraphs without Short Cycles.
SIAM J. Discrete Math., 2015

Walker-Breaker Games.
SIAM J. Discrete Math., 2015

Long paths and cycles in random subgraphs of graphs with large minimum degree.
Random Struct. Algorithms, 2015

Generating random graphs in biased Maker-Breaker games.
Random Struct. Algorithms, 2015

Biased games on random boards.
Random Struct. Algorithms, 2015

Cycles and matchings in randomly perturbed digraphs and hypergraphs.
Electronic Notes in Discrete Mathematics, 2015

Some Remarks on Rainbow Connectivity.
Electronic Notes in Discrete Mathematics, 2015

Decomposing Random Graphs into Few Cycles and Edges.
Combinatorics, Probability & Computing, 2015

Random-Player Maker-Breaker games.
Electr. J. Comb., 2015

Contagious Sets in Expanders.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014
On covering expander graphs by hamilton cycles.
Random Struct. Algorithms, 2014

Long Paths and Cycles in Random Subgraphs of $\mathcal{H}$-free Graphs.
Electr. J. Comb., 2014

Packing Tree Factors in Random and Pseudo-random Graphs.
Electr. J. Comb., 2014

Smoothed Analysis on Connected Graphs.
Proceedings of the Approximation, 2014

2013
On the Number of Hamilton Cycles in Sparse Random Graphs.
SIAM J. Discrete Math., 2013

The phase transition in random graphs: A simple proof.
Random Struct. Algorithms, 2013

Longest cycles in sparse random digraphs.
Random Struct. Algorithms, 2013

Avoider-Enforcer games played on edge disjoint hypergraphs.
Discrete Mathematics, 2013

On the Non-Planarity of a Random Subgraph.
Combinatorics, Probability & Computing, 2013

The Biased Odd Cycle Game.
Electr. J. Comb., 2013

Comparing the strength of query types in property testing: The case of k-colorability.
Computational Complexity, 2013

2012
Optimal Packings of Hamilton Cycles in Sparse Random Graphs.
SIAM J. Discrete Math., 2012

Creating Small Subgraphs in Achlioptas Processes With Growing Parameter.
SIAM J. Discrete Math., 2012

Sharp threshold for the appearance of certain spanning trees in random graphs.
Random Struct. Algorithms, 2012

Packing hamilton cycles in random and pseudo-random hypergraphs.
Random Struct. Algorithms, 2012

Variations on cops and robbers.
Journal of Graph Theory, 2012

Long cycles in subgraphs of (pseudo)random directed graphs.
Journal of Graph Theory, 2012

The size Ramsey number of a directed path.
J. Comb. Theory, Ser. B, 2012

Fast embedding of spanning trees in biased Maker-Breaker games.
Eur. J. Comb., 2012

Biased orientation games.
Discrete Mathematics, 2012

Fast Strategies In Maker-Breaker Games Played on Random Boards.
Combinatorics, Probability & Computing, 2012

On the Number of Hamilton Cycles in Pseudo-Random Graphs.
Electr. J. Comb., 2012

Expanders are universal for the class of all spanning trees.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011
On the Resilience of Hamiltonicity and Optimal Packing of Hamilton Cycles in Random Graphs.
SIAM J. Discrete Math., 2011

Regular induced subgraphs of a random Graph.
Random Struct. Algorithms, 2011

Ramsey games with giants.
Random Struct. Algorithms, 2011

Fast embedding of spanning trees in biased Maker-Breaker games.
Electronic Notes in Discrete Mathematics, 2011

Global Maker-Breaker games on sparse graphs.
Eur. J. Comb., 2011

Local Resilience and Hamiltonicity Maker-Breaker Games in Random Regular Graphs.
Combinatorics, Probability & Computing, 2011

The Number of f-Matchings in Almost Every Tree is a Zero Residue.
Electr. J. Comb., 2011

Packing tight Hamilton cycles in 3-uniform hypergraphs.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Hitting time results for Maker-Breaker games.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010
Resilient Pancyclicity of Random and Pseudorandom Graphs.
SIAM J. Discrete Math., 2010

Embedding Spanning Trees in Random Graphs.
SIAM J. Discrete Math., 2010

Hamilton Cycles in Random Graphs with a Fixed Degree Sequence.
SIAM J. Discrete Math., 2010

Offline thresholds for Ramsey-type games on random graphs.
Random Struct. Algorithms, 2010

Hamiltonicity thresholds in Achlioptas processes.
Random Struct. Algorithms, 2010

Why Almost All k-Colorable Graphs Are Easy to Color.
Theory Comput. Syst., 2010

The rainbow connection of a graph is (at most) reciprocal to its minimum degree.
Journal of Graph Theory, 2010

A note on regular Ramsey graphs.
Journal of Graph Theory, 2010

Avoider-Enforcer: The rules of the game.
J. Comb. Theory, Ser. A, 2010

Combinatorics, Probability & Computing, 2010

2009
Spanning Directed Trees with Many Leaves.
SIAM J. Discrete Math., 2009

Equitable coloring of random graphs.
Random Struct. Algorithms, 2009

Avoiding small subgraphs in Achlioptas processes.
Random Struct. Algorithms, 2009

A sharp threshold for the Hamilton cycle Maker-Breaker game.
Random Struct. Algorithms, 2009

Fast winning strategies in Maker-Breaker games.
J. Comb. Theory, Ser. B, 2009

Fast Winning Strategies in Avoider-Enforcer Games.
Graphs and Combinatorics, 2009

Avoider-Enforcer: The Rules of the Game.
Electronic Notes in Discrete Mathematics, 2009

Electronic Notes in Discrete Mathematics, 2009

Vertex percolation on expander graphs.
Eur. J. Comb., 2009

Random regular graphs of non-constant degree: Concentration of the chromatic number.
Discrete Mathematics, 2009

On the Random Satisfiable Process.
Combinatorics, Probability & Computing, 2009

Perfectly Balanced Partitions of Smoothed Graphs.
Electr. J. Comb., 2009

Hamilton cycles in highly connected and expanding graphs.
Combinatorica, 2009

On smoothed k-CNF formulas and the Walksat algorithm.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Hierarchy Theorems for Property Testing.
Proceedings of the Approximation, 2009

2008
Planarity, Colorability, and Minor Games.
SIAM J. Discrete Math., 2008

Large Nearly Regular Induced Subgraphs.
SIAM J. Discrete Math., 2008

Corrigendum: On fractional K-factors of random graphs.
Random Struct. Algorithms, 2008

The isoperimetric constant of the random graph process.
Random Struct. Algorithms, 2008

Winning Fast in Sparse Graph Construction Games.
Combinatorics, Probability & Computing, 2008

Biased Positional Games and Small Hypergraphs with Large Covers.
Electr. J. Comb., 2008

On Rainbow Trees and Cycles.
Electr. J. Comb., 2008

Comparing the strength of query types in property testing: the case of testing k-colorability.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Small Sample Spaces Cannot Fool Low Degree Polynomials.
Proceedings of the Approximation, 2008

2007
Approximation algorithms and hardness results for cycle packing problems.
ACM Trans. Algorithms, 2007

On fractional K-factors of random graphs.
Random Struct. Algorithms, 2007

Avoider-Enforcer games.
J. Comb. Theory, Ser. A, 2007

Addendum to "Scalable secure storage when half the system is faulty" [Inform. Comput 174 (2)(2002) 203-213].
Inf. Comput., 2007

Fast winning strategies in positional games.
Electronic Notes in Discrete Mathematics, 2007

Bart-Moe games, JumbleG and discrepancy.
Eur. J. Comb., 2007

On the Chromatic Number of Random Graphs with a Fixed Degree Sequence.
Combinatorics, Probability & Computing, 2007

Embedding nearly-spanning bounded degree trees.
Combinatorica, 2007

Why Almost All k -Colorable Graphs Are Easy.
Proceedings of the STACS 2007, 2007

Parameterized Algorithms for Directed Maximum Leaf Problems.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Better Algorithms and Bounds for Directed Maximum Leaf Problems.
Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

2006
On smoothed analysis in dense graphs and formulas.
Random Struct. Algorithms, 2006

Coloring complete bipartite graphs from random lists.
Random Struct. Algorithms, 2006

Almost universal graphs.
Random Struct. Algorithms, 2006

On the asymptotic value of the choice number of complete multi-partite graphs.
Journal of Graph Theory, 2006

Preface.
Eur. J. Comb., 2006

Solving random satisfiable 3CNF formulas in expected polynomial time.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Testing triangle-freeness in general graphs.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Semirandom Models as Benchmarks for Coloring Algorithms.
Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, 2006

2005
Testing Reed-Muller codes.
IEEE Trans. Information Theory, 2005

The Strong Chromatic Index of Random Graphs.
SIAM J. Discrete Math., 2005

Recognizing More Unsatisfiable Random k-SAT Instances Efficiently.
SIAM J. Comput., 2005

On packing Hamilton cycles in ?-regular graphs.
J. Comb. Theory, Ser. B, 2005

Discrepancy Games.
Electr. J. Comb., 2005

Approximation algorithms for cycle packing problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On the random 2-stage minimum spanning tree.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
The emergence of a giant component in random subgraphs of pseudo-random graphs.
Random Struct. Algorithms, 2004

Adding random edges to dense graphs.
Random Struct. Algorithms, 2004

Algorithms with large domination ratio.
J. Algorithms, 2004

Colouring powers of cycles from random lists.
Eur. J. Comb., 2004

Triangle Factors In Sparse Pseudo-Random Graphs.
Combinatorica, 2004

Bounds on distance distributions in codes of known size.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

2003
Covering codes with improved density.
IEEE Trans. Information Theory, 2003

On the probability of independent sets in random graphs.
Random Struct. Algorithms, 2003

Sparse pseudo-random graphs are Hamiltonian.
Journal of Graph Theory, 2003

Induced subgraphs of prescribed size.
Journal of Graph Theory, 2003

Generalized hashing and parent-identifying codes.
J. Comb. Theory, Ser. A, 2003

Maximum cuts and judicious partitions in graphs without short cycles.
J. Comb. Theory, Ser. B, 2003

Approximate coloring of uniform hypergraphs.
J. Algorithms, 2003

The Largest Eigenvalue Of Sparse Random Graphs.
Combinatorics, Probability & Computing, 2003

Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.
Combinatorics, Probability & Computing, 2003

Tight Bounds for Testing Bipartiteness in General Graphs.
Proceedings of the Approximation, 2003

Testing Low-Degree Polynomials over GF(2(.
Proceedings of the Approximation, 2003

2002
Upper bounds on the rate of LDPC Codes.
IEEE Trans. Information Theory, 2002

Testing k-colorability.
SIAM J. Discrete Math., 2002

Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time.
J. Comb. Optim., 2002

Deciding k-colorability in expected polynomial time.
Inf. Process. Lett., 2002

Hamilton cycles in random subgraphs of pseudo-random graphs.
Discrete Mathematics, 2002

Fractional Planks.
Discrete & Computational Geometry, 2002

A Sharp Threshold For Network Reliability.
Combinatorics, Probability & Computing, 2002

Sparse Graphs Usually Have Exponentially Many Optimal Colorings.
Electr. J. Comb., 2002

2001
Random regular graphs of high degree.
Random Struct. Algorithms, 2001

Choosability in Random Hypergraphs.
J. Comb. Theory, Ser. B, 2001

Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods.
Proceedings of the STACS 2001, 2001

Approximating coloring and maximum independent sets in 3-uniform hypergraphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000
Sharp thresholds for certain Ramsey properties of random graphs.
Random Struct. Algorithms, 2000

Long cycles in critical graphs.
Journal of Graph Theory, 2000

The Choice Number Of Dense Random Graphs.
Combinatorics, Probability & Computing, 2000

Approximating the Independence Number and the Chromatic Number in Expected Polynominal Time.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Scalable Secure Storage when Half the System Is Faulty.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Two-coloring Random Hypergraphs.
Proceedings of the ICALP Workshops 2000, 2000

1999
Coloring Graphs with Sparse Neighborhoods.
J. Comb. Theory, Ser. B, 1999

List Coloring of Random and Pseudo-Random Graphs.
Combinatorica, 1999

Regular Languages Are Testable with a Constant Number of Queries.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Efficient Testing of Large Graphs.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
The chromatic numbers of random hypergraphs.
Random Struct. Algorithms, 1998

Coloring Random Graphs.
Inf. Process. Lett., 1998

A lower bound for irredundant Ramsey numbers.
Discrete Mathematics, 1998

An Improved Bound on the Minimal Number of Edges in Color-Critical Graphs.
Electr. J. Comb., 1998

Finding a Large Hidden Clique in a Random Graph.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Approximate Coloring of Uniform Hypergraphs (Extended Abstract).
Proceedings of the Algorithms, 1998

1997
Approximate Set Covering in Uniform Hypergraphs.
J. Algorithms, 1997

Constructive Bounds for a Ramsey-Type Problem.
Graphs and Combinatorics, 1997

Almost perfect matchings in random uniform hypergraphs.
Discrete Mathematics, 1997

Triangle Factors in Random Graphs.
Combinatorics, Probability & Computing, 1997

On the Minimal Number of Edges in Color-Critical Graphs.
Combinatorica, 1997

The Concentration of the Chromatic Number of Random Graphs.
Combinatorica, 1997

1996
Perfect fractional matchings in random hypergraphs.
Random Struct. Algorithms, 1996

On k-saturated graphs with restrictions on the degrees.
Journal of Graph Theory, 1996

On a Theorem of Lovász on Covers in tau-Partite Hypergraphs.
Combinatorica, 1996

1995
Bounding Ramsey Numbers through Large Deviation Inequalities.
Random Struct. Algorithms, 1995

On the Edge Distribution in Triangle-free Graphs.
J. Comb. Theory, Ser. B, 1995

On a conjecture of Tuza about packing and covering of triangles.
Discrete Mathematics, 1995

1994
Ks-Free Graphs Without Large Kr-Free Subgraphs.
Combinatorics, Probability & Computing, 1994