Michael Krivelevich's Papers

1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024
Preprints

TOP
1994

  • M. Krivelevich,
    • K^s-free graphs without large K^r-free subgraphs,
    Combinatorics, Probability and Computing 3 (1994), 349-354.  

    TOP
    1995

  • M. Krivelevich,
    • On a conjecture of Tuza about packing and covering of triangles,
    Discrete Mathematics 142 (1995), 281-286.  
  • M. Krivelevich,
    • On the edge distribution of triangle-free graphs,
    Journal of Combinatorial Theory, Ser. B 63 (1995), 245-260.  
  • M. Krivelevich,
    • Bounding Ramsey numbers through large deviation inequalities,
    Random Structures and Algorithms 7 (1995), 145-155.  

    TOP
    1996

  • R. Aharoni, R. Holzman and M. Krivelevich,
    • On a Theorem of Lovasz on covers in r-partite hypergraphs,
    Combinatorica 16 (1996), 149-174.  
  • N. Alon, P. Erdos, R. Holzman and M. Krivelevich,
    • On k-saturated graphs with restrictions on the degrees,
    Journal of Graph Theory 23 (1996), 1-20.  
  • M. Krivelevich,
    • Perfect fractional matchings in random uniform hypergraphs,
    Random Structures and Algorithms 9 (1996), 317-334.  

    TOP
    1997

  • M. Krivelevich,
    • Almost perfect matchings in random uniform hypergraphs,
    Discrete Mathematics 170 (1997), 259-263.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Subgraphs with a large cochromatic number,
    Journal of Graph Theory 26 (1997), 295-297.  
  • M. Krivelevich,
    • Triangle factors in random graphs,
    Combinatorics, Probability and Computing 6 (1997), 337-347.  
  • N. Alon and M. Krivelevich,
    • Constructive bounds for a Ramsey-type problem,
    Graphs and Combinatorics 13 (1997), 217-225.  
  • M. Krivelevich,
    • Approximate set covering in uniform hypergraphs,
    Journal of Algorithms 25 (1997), 118-143.  
  • N. Alon and M. Krivelevich,
    • The concentration of the chromatic number of random graphs,
    Combinatorica 17 (1997), 303-313.  
  • M. Krivelevich,
    • On the minimal number of edges in color-critical graphs,
    Combinatorica 17 (1997), 401-426.  

    TOP
    1998

  • M. Krivelevich,
    • An improved bound on the minimal number of edges in color-critical graphs,
    Electronic J. Combinatorics, Volume 5(1) (1998), paper R4.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Finding a large hidden clique in a random graph,
    Proceedings of the $9^{th}$ Symposium on Discrete Algorithms (SODA'98), 594-598. Journal version: Random Structures and Algorithms, 13 (1998), 457-466.  
  • M. Krivelevich,
    • A lower bound for irredundant Ramsey numbers,
    Discrete Mathematics 183 (1998), 185-192.  
  • M. Krivelevich and B. Sudakov,
    • The chromatic numbers of random hypergraphs,
    Random Structures and Algorithms 12 (1998), 381-403.  
  • M. Krivelevich and B. Sudakov,
    • Coloring random graphs,
    Information Processing Letters 67 (1998), 71-74.  
  • M. Krivelevich and B. Sudakov,
    • Approximate coloring of uniform hypergraphs,
    Proceedings of the $6^{th}$ Annual European Symposium on Algorithms (ESA'98), Lecture Notes in Computer Science 1461, 477-489. Journal version: Journal of Algorithms 49 (2003), 2-12.  
  • N. Alon and M. Krivelevich,
    • The choice number of random bipartite graphs,
    Annals of Combinatorics 2 (1998), 291-297.  

    TOP
    1999

  • N. Alon, M. Krivelevich and B. Sudakov,
    • Coloring graphs with sparse neighborhoods,
    Journal of Combinatorial Theory Ser. B 77 (1999), 73-82.  
  • N. Alon, E. Fischer, M. Krivelevich and M. Szegedy,
    • Efficient testing of large graphs,
    Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS'99), IEEE Press 1999, 656-666. Journal version: Combinatorica 20 (2000), 451-476.  
  • N. Alon, M. Krivelevich, I. Newman and M. Szegedy,
    • Regular languages are testable with a constant number of queries,
    Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS'99), IEEE Press 1999, 645-655. Journal version: SIAM Journal on Computing 30 (2001), 1842-1862.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • List coloring of random and pseudo-random graphs,
    Combinatorica 19 (1999), 453-472.  

    TOP
    2000

  • M. Krivelevich,
    • The choice number of dense random graphs,
    Combinatorics, Probability and Computing 9 (2000), 19-26.  
  • M. Krivelevich and V. H. Vu,
    • Approximating the independence number and the chromatic number in expected polynomial time,
    27th International Colloquium on Automata, Languages and Programming (ICALP'2000), Lecture Notes in Computer Science 1853, 13-24. Also: Journal of Combinatorial Optimization 6 (2002), 143-155.  
  • N. Alon, H. Kaplan, M. Krivelevich, D. Malkhi and J. Stern,
    • Scalable secure storage when half the system is faulty,
    27th International Colloquium on Automata, Languages and Programming (ICALP'2000), Lecture Notes in Computer Science 1853, 576-587. Journal version: Information and Computation 174 (2002), 203-213.  
  • D. Achlioptas, J. H. Kim, M. Krivelevich and P. Tetali,
    • Two-coloring random hypergraphs,
    4th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM'2000), ICALP Workshops 2000, Proceedings in Informatics 8, Carleton Scientific, 85-96. Journal version: Random Structures and Algorithms 20 (2002), 249-259.  
  • E. Friedgut and M. Krivelevich,
    • Sharp thresholds for certain Ramsey properties of random graphs,
    Random Structures and Algorithms 17 (2000), 1-19.  
  • N. Alon, M. Krivelevich and P. Seymour,
    • Long cycles in critical graphs,
    Journal of Graph Theory 35 (2000), 193-196.  

    TOP
    2001

  • M. Krivelevich, R. Nathaniel and B. Sudakov,
    • Approximating coloring and maximum independent set in 3-uniform hypergraphs,
    Proceedings of the 12th Symposium on Discrete Algorithms (SODA'2001), 327-328. Journal version: Journal of Algorithms 41 (2001), 99-113.  
  • A. Goerdt and M. Krivelevich,
    • Efficient recognition of random unsatisfiable k-SAT instances by spectral methods,
    Proceedings of the 18th International Symposium on Theoretical Aspects of Computer Science (STACS'2001), Lecture Notes in Computer Science 2010, 294-304.  
  • M. Krivelevich, B. Sudakov, V. H. Vu and N. Wormald,
    • Random regular graphs of high degree,
    Random Structures and Algorithms 18 (2001), 346-363.  
  • M. Krivelevich and V. H. Vu,
    • Choosability in random hypergraphs,
    Journal of Combinatorial Theory Ser. B 83 (2001), 241-257.  

    TOP
    2002

  • M. Krivelevich,
    • Deciding k-colorability in expected polynomial time,
    Information Processing Letters 81 (2002), 1-6.  
  • N. Alon and M. Krivelevich,
    • Testing k-colorability,
    SIAM Journal on Discrete Mathematics 15 (2002), 211-227.  
  • R. Aharoni, R. Holzman, M. Krivelevich and R. Meshulam,
    • Fractional planks,
    Discrete and Computational Geometry 27 (2002), 585-602.  
  • M. Krivelevich,
    • Sparse graphs usually have exponentially many optimal colorings.
    Electronic Journal of Combinatorics 9 (2002), publ. R27, 8pp.  
  • N. Alon, G. Cohen, M. Krivelevich and S. Litsyn,
    • Generalized hashing and applications to digital fingerprinting.
    Proceedings of the IEEE International Symposium on Information Theory (ISIT) 2002, p. 436. Journal version: Journal of Combinatorial Theory Series A 104 (2003), 207-215.  
  • D. Burshtein, M. Krivelevich, S. Litsyn and G. Miller,
    • Upper bounds on the rate of LDPC codes.
    IEEE Transactions on Information Theory 48 (2002), 2437-2449.  
  • M. Krivelevich,
    • Coloring random graphs - an algorithmic perspective.
    Proceedings of the 2nd Colloquium on Mathematics and Computer Science (MathInfo'2002), B. Chauvin et al. Eds., Birkhauser, Basel, 2002, 175-195.  
  • A. Frieze and M. Krivelevich,
    • Hamilton cycles in random subgraphs of pseudo-random graphs,
    Discrete Mathematics 256 (2002), 137-150.  
  • M. Krivelevich, B. Sudakov and V. H. Vu,
    • A sharp threshold for network reliability,
    Combinatorics, Probability and Computing 11 (2002), 465-474.  
  • N. Alon, M. Krivelevich and V. H. Vu,
    • On the concentration of eigenvalues of random symmetric matrices,
    Israel Journal of Mathematics 131 (2002), 259-267.  

    TOP
    2003

  • M. Krivelevich, B. Sudakov, V. H. Vu and N. Wormald,
    • On the probability of independent sets in random graphs.
    Random Structures and Algorithms 22 (2003), 1-14.  
  • M. Krivelevich and B. Sudakov,
    • Sparse pseudo-random graphs are Hamiltonian.
    Journal of Graph Theory 42 (2003), 17-33.  
  • M. Krivelevich and B. Sudakov,
    • The largest eigenvalue of sparse random graphs.
    Combinatorics, Probability and Computing 12 (2003), 61-72.  
  • G. Cohen, M. Krivelevich and S. Litsyn,
    • Bounds on distance distributions in codes of given size.
    Chapter 4 of "Communication, Information and Network Security", V. Bhargava et al., pp. 33-41.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Induced subgraphs of prescribed size.
    Journal of Graph Theory 43 (2003), 239-251.  
  • N. Alon, B. Bollobas, M. Krivelevich and B. Sudakov,
    • Maximum cuts and judicious partitions in graphs without short cycles.
    Journal of Combinatorial Theory Ser. B 88 (2003), 329-346.  
  • M. Krivelevich, B. Sudakov and V. H. Vu,
    • Covering codes with improved density.
    IEEE Transactions on Information Theory 49 (2003), 1812-1815.  
  • T. Kaufman, M. Krivelevich and D. Ron,
    • Tight bounds for testing bipartiteness in general graphs.
    Lecture Notes in Computer Science 2764, 341-353. Journal version: SIAM Journal on Computing 33 (2004), 1441-1483.  
  • N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn and D. Ron,
    • Testing low-degree polynomials over GF(2).
    Lecture Notes in Computer Science 2764, 188-199. Journal version. IEEE Transactions on Information Theory 51 (2005), 4032-4039.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Turan numbers of bipartite graphs and related Ramsey-type questions.
    Combinatorics, Probability and Computing 12 (2003), 477-494.  

    TOP
    2004

  • A. Frieze, M. Krivelevich and R. Martin,
    • The emergence of a giant component in random subgraphs of pseudo-random graphs.
    Random Structures and Algorithms 24 (2004), 42-50.  
  • N. Alon, G. Gutin and M. Krivelevich,
    • Algorithms with large domination ratio.
    Journal of Algorithms 50 (2004), 118-131.  
  • T. Bohman, A. Frieze, M. Krivelevich and R. Martin,
    • Adding random edges to dense graphs.
    Random Structures and Algorithms 24 (2004), 105-117.  
  • M. Krivelevich, S. Litsyn and A. Vardy,
    • A lower bound on the density of sphere packings via graph theory.
    International Mathematical Research Notices 43 (2004), 2271-2279.  
  • M. Krivelevich, B. Sudakov and T. Szabo,
    • Triangle factors in sparse pseudo-random graphs.
    Combinatorica 24 (2004), 403-426.  
  • M. Krivelevich and A. Nachmias,
    • Colouring powers of cycles from random lists.
    European Journal of Combinatorics 25 (2004), 961-968.  

    TOP
    2005

  • A. Ashikhmin, G. Cohen, M. Krivelevich and S. Litsyn,
    • Bounds on distance distributions in codes of known size.
    IEEE Transactions on Information Theory 51 (2005), 250-258.  
  • A. Flaxman, A. Frieze and M. Krivelevich,
    • On the random 2-stage minimum spanning tree.
    Proceedings of the 16th Symposium on Discrete Algorithms (SODA'2005), 919-926. Journal version. Random Structures and Algorithms 28 (2006), 24-36  
  • M. Krivelevich, Z. Nutov and R. Yuster,
    • Approximation algorithms for cycle packing problems.
    Proceedings of the 16th Symposium on Discrete Algorithms (SODA'2005), 556-561.  
  • A. Frieze and M. Krivelevich,
    • On packing Hamilton cycles in epsilon-regular graphs.
    Journal of Combinatorial Theory Series B 94 (2005), 159-172.  
  • N. Alon, M. Krivelevich, J. Spencer and T. Szabo,
    • Discrepancy games.
    Electronic Journal of Combinatorics Volume 12 (1) (2005), publ. R51.  
  • J. Friedman, A. Goerdt and M. Krivelevich,
    • Recognizing more unsatisfiable random k-SAT instances efficiently.
    SIAM Journal on Computing 35 (1005), 408-430.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • MaxCut in H-free graphs.
    Combinatorics, Probability and Computing 14 (2005), 629-647.  
  • A. Frieze, M. Krivelevich, O. Pikhurko and T. Szabo,
    • The game of JumbleG.
    Combinatorics, Probability and Computing 14 (2005), 783-793.  
  • A. Frieze, M. Krivelevich and B. Sudakov,
    • The strong chromatic index of random graphs.
    SIAM Journal on Discrete Mathematics 19 (2005), 719-727.  

    TOP
    2006

  • N. Alon, T. Kaufman, M. Krivelevich and D. Ron,
    • Testing triangle-freeness in general graphs.
    Proceedings of the 17th Symposium on Discrete Algorithms (SODA'06), 279-288. Journal version: SIAM Journal on Discrete Mathematics 22 (2008), 786-819.  
  • M. Krivelevich and D. Vilenchik,
    • Solving random satisfiable 3CNF formulas in expected polynomial time.
    Proceedings of the 17th Symposium on Discrete Algorithms (SODA'06), 454-463.  
  • M. Krivelevich and D. Vilenchik,
    • Semirandom models as benchmarks for coloring algorithms.
    Proceedings of 3rd Workshop on Analytic Algorithmics and Combinatorics (ANALCO'06), 211--221.  
  • N. Gazit and M. Krivelevich,
    • On the asymptotic value of the choice number of complete multi-partite graphs.
    Journal of Graph Theory 52 (2006), 123-134.  
  • M. Krivelevich and B. Sudakov,
    • Pseudo-random graphs.
    More sets, graphs and numbers, E. Gyori, G. O. H. Katona and L. Lovasz, Eds., Bolyai Society Mathematical Studies Vol. 15, 199-262.  
  • A. Frieze and M. Krivelevich,
    • Almost universal graphs.
    Random Structures and Algorithms 28 (2006), 499-510.  
  • M. Krivelevich, B. Sudakov and P. Tetali,
    • On smoothed analysis in dense graphs and formulas.
    Random Structures and Algorithms 29 (2006), 180-193.  
  • M. Krivelevich and A. Nachmias,
    • Colouring complete bipartite graphs from random lists.
    Random Structures and Algorithms 29 (2006), 436-449.  

    TOP
    2007

  • A. Coja-Oghlan, M. Krivelevich and D. Vilenchik,
    • Why almost all k-colorable graphs are easy.
    Proceedings of the 24th International Symposium on Theoretical Computer Science (STACS'2007), Lecture Notes in Computer Science 4393, 121-132. Journal version: Theory of Computing Systems 46 (2010), 523-565.  
  • D. Hefetz, M. Krivelevich and T. Szabo,
    • BartMoe games, JumbleG and discrepancy.
    European Journal of Combinatorics 28 (2007), 1131-1143.  
  • S. Haber and M. Krivelevich,
    • On fractional K-factors of random graphs.
    Random Structures and Algorithms 30 (2007), 441-463.  
  • D. Hefetz, M. Krivelevich and T. Szabo,
    • Avoider-Enforcer games.
    Journal of Combinatorial Theory Series A 114 (2007), 840-853.  
  • A. Frieze, M. Krivelevich and C. Smyth,
    • On the chromatic number of random graphs with a fixed degree sequence.
    Combinatorics, Probability and Computing 16 (2007), 733-746.  
  • N. Alon, F. Fomin, G. Gutin, M. Krivelevich and S. Saurabh, Parametrized algorithms for directed maximum leaf problems.
    Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'2007), Lecture Notes in Computer Science 4596, 352-362.  
  • M. Krivelevich, Z. Nutov, M. Salavatipour, J. Verstraete and R. Yuster,
    • Approximation algorithms and hardness results for cycle packing problems.
    ACM Transactions on Algorithms, Volume 3 (2007), Article 48.  
  • N. Alon, F. Fomin, G. Gutin, M. Krivelevich and S. Saurabh, Better algorithms and bounds for directed maximum leaf problems.
    Proceedings of the Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'2007), Lecture Notes in Computer Science 4855, 316-327. Journal version: Spanning directed trees with many leaves. SIAM Journal on Discrete Mathematics 23 (2009), 466-476.  
  • A. Coja-Oghlan, M. Krivelevich and D. Vilenchik, Why almost all k-CNF formulas are easy.
    Conference on Analysis of Algorithms (AOFA'2007), Discrete Mathematics and Theoretical Computer Science (DMTCS), AH, 2007, 89-102.  
  • N. Alon, M. Krivelevich and B. Sudakov,
    • Embedding nearly spanning bounded degree trees.
    Combinatorica 27 (2007), 629-644.  

    TOP
    2008

  • I. Benjamini, S. Haber, M. Krivelevich and E. Lubetzky,
    • The isoperimetric constant of the random graph process.
    Random Structures and Algorithms 32 (2008), 101-114.  
  • I. Ben-Eliezer, T. Kaufman, M. Krivelevich and D. Ron, Comparing the strength of query types in property testing: the case of testing k-colorability.
    Proceedings of the 19th Symposium on Discrete Algorithms (SODA'08), 1213-1222. Journal version: Computational Complexity 22 (2013), 89-135.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo,
    • Planarity, colorability and minor games.
    SIAM Journal on Discrete Mathematics 22 (2008), 194-212.  
  • A. Frieze and M. Krivelevich, On rainbow trees and cycles.
    Electronic Journal of Combinatorics, Vol. 15 (1) (2008), publ. R59.  
  • M. Krivelevich and T. Szabo, Biased positional games and small hypergraphs with large covers.
    Electronic Journal of Combinatorics, Vol. 15 (1) (2008), publ. R70.  
  • A. Frieze and M. Krivelevich,
    • On two Hamilton cycle problems in random graphs.
    Israel Journal of Mathematics 166 (2008), 221-234.  
  • N. Alon, I. Ben-Eliezer and M. Krivelevich, Small sample spaces cannot fool low degree polynomials.
    Proceedings of the 12th International Workshop on Randomized Techniques in Computation (RANDOM'2008), Lecture Notes in Computer Science 5171 (2008), 266-275.  
  • N. Alon, M. Krivelevich and B. Sudakov, Large nearly regular induced subgraphs.
    SIAM Journal on Discrete Mathematics 22 (2008), 1325-1337.  
  • O. Feldheim and M. Krivelevich, Winning fast in sparse graph construction games.
    Combinatorics, Probability and Computing 17 (2008), 781-791.  
  • N. Alon and M. Krivelevich,
    • Extremal and Probabilistic Combinatorics.
    In: Princeton Compantion to Mathematics, W. T. Gowers, Ed., Princeton University Press 2008, pp. 562-575.  

    TOP
    2009

  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, A sharp threshold for the Hamilton cycle Maker-Breaker game.
    Random Structures and Algorithms 34 (2009), 112-122.  
  • M. Krivelevich, P.-S. Loh and B. Sudakov, Avoiding small subgraphs in Achlioptas processes.
    Random Structures and Algorithms 34 (2009), 165-195.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo,
    • Fast winning strategies in Maker-Breaker games.
    Journal of Combinatorial Theory Series B 99 (2009), 39-47.  
  • S. Ben-Shimon and M. Krivelevich,
    • Vertex percolation on expander graphs.
    European Journal of Combinatorics 30 (2009), 339-350.  
  • A. Coja-Oghlan, U. Feige, A. Frieze, M. Krivelevich and D. Vilenchik, On smoothed k-CNF formulas and the Walksat algorithm.
    Proceedings of the 20th Symposium on Discrete Algorithms (SODA'09), 451-460.  
  • I. Ben-Eliezer and M. Krivelevich, Perfectly balanced partitions of smoothed graphs.
    Electronic Journal of Combinatorics, Vol. 16 (1) (2009), note N14.  
  • S. Ben-Shimon and M. Krivelevich,
    • Random regular graphs of non-constant degree: concentration of the chromatic number.
    Discrete Mathematics 309 (2009), 4149-4161.  
  • M. Krivelevich and B. Sudakov,
    • Minors in expanding graphs.
    Geometric and Functional Analysis 19 (2009), 294-331.  
  • M. Krivelevich and B. Patkos, Equitable coloring of random graphs.
    Random Structures and Algorithms 35 (2009), 83-99.  
  • O. Goldreich, M. Krivelevich, I. Newman and E.Rozenberg, Hierarchy theorems for property testing.
    Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM'2009), Lecture Notes in Computer Science 5867 (2009), 504-519. Journal version: Computational Complexity 21 (2012), 129-192.  
  • M. Krivelevich, B. Sudakov and D. Vilenchik, On the random satisfiable process.
    Combinatorics, Probability and Computing 18 (2009), 775-801.  
  • D. Hefetz, M. Krivelevich and T. Szabo,
    • Hamilton cycles in highly connected and expanding graphs.
    Combinatorica 29 (2009), 547-568.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Fast winning strategies in Avoider-Enforcer games.
    Graphs and Combinatorics 25 (2009), 533-544.  

    TOP
    2010

  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Avoider - Enforcer: the rules of the game.
    Journal of Combinatorial Theory Series A 117 (2010), 152-163.  
  • M. Krivelevich, R. Spohel and A. Steger, Offline thresholds for Ramsey-type games on random graphs.
    Random Structures and Algorithms 36 (2010), 57--79.  
  • M. Krivelevich and R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree.
    Journal of Graph Theory 63 (2010), 185-191.  
  • M. Krivelevich, C. Lee and B. Sudakov, Resilient pancyclicity of random and pseudo-random graphs.
    SIAM Journal on Discrete Mathematics 24 (2010), 1-16.  
  • C. Cooper, A. Frieze and M. Krivelevich, Hamilton cycles in random graphs with a fixed degree sequence.
    SIAM Journal on Discrete Mathematics 24 (2010), 558-569.  
  • N. Alon, D. Hefetz and M. Krivelevich, Playing to retain the advantage.
    Combinatorics, Probability and Computing 19 (2010), 481-491.  
  • N. Alon, S. Ben-Shimon and M. Krivelevich, A note on regular Ramsey graphs.
    Journal of Graph Theory 64 (2010), 244-249.  
  • M. Krivelevich, E. Lubetzky and B. Sudakov, Hamiltonicity thresholds in Achlioptas processes.
    Random Structures and Algorithms 37 (2010), 1-24.  
  • M. Krivelevich, Embedding spanning trees in random graphs.
    SIAM Journal on Discrete Mathematics 24 (2010), 1495-1500.  
  • S. Haber and M. Krivelevich, The logic of random regular graphs.
    Journal of Combinatorics 1 (2010), 389-440.  

    TOP
    2011

  • M. Krivelevich, The critical bias for the Hamiltonicity game is (1+o(1))n/ln n.
    Journal of the American Mathematical Society 24 (2011), 125-131.  
  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Global Maker-Breaker games on sparse graphs.
    European Journal of Combinatorics 32 (2011), 162-177.  
  • T. Bohman, A. Frieze, M. Krivelevich, P.-S. Loh and B. Sudakov, Ramsey games with giants.
    Random Structures and Algorithms 38 (2011), 1-32.  
  • S. Ben-Shimon, M. Krivelevich and B. Sudakov, Local resilience and Hamiltonicity Maker-Breaker games in random regular graphs.
    Combinatorics, Probability and Computing 20 (2011), 173-211.  
  • S. Ben-Shimon, A. Ferber, D. Hefetz and M. Krivelevich, Hitting time results for Maker-Breaker games.
    Proceedings of the 22nd Symposium on Discrete Algorithms (SODA'11), 900-912. Journal version. Random Structures and Algorithms 41 (2012), 23-46.  
  • A. Frieze, M. Krivelevich and P.-S. Loh, Packing tight Hamilton cycles in 3-uniform hypergraphs.
    Proceedings of the 22nd Symposium on Discrete Algorithms (SODA'11), 913-932. Journal version: Random Structures and Algorithms 40 (2012), 269-300.  
  • N. Alon, S. Haber and M. Krivelevich, The number of F-matchings in almost every tree is a zero residue.
    Electronic Journal of Combinatorics, Volume 18 (1) (2011), publication P30.  
  • M. Krivelevich, B. Sudakov and N. Wormald, Regular induced subgraphs of a random graph.
    Random Structures and Algorithms 28 (2011), 235-250.  
  • J. Balogh, B. Bollobas, M. Krivelevich, T. Muller and M. Walters, Hamilton cycles in random geometric graphs.
    Annals of Applied Probability 21 (2011), 1053-1072.  
  • S. Ben-Shimon, M. Krivelevich and B. Sudakov, On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs.
    SIAM Journal on Discrete Mathematics 25 (2011), 1176-1193.  

    TOP
    2012

  • D. Johannsen, M. Krivelevich and W. Samotij, Expanders are universal for the class of all spanning trees.
    Proceedings of the 23rd Symposium on Discrete Algorithms (SODA'12), 1539-1551. Journal version: Combinatorics, Probability and Computing 22 (2013), 253-281.  
  • M. Krivelevich, On the number of Hamilton cycles in pseudo-random graphs.
    Electronic Journal of Combinatorics, Volume 19 (2012), publication P25.  
  • A. Ferber, D. Hefetz and M. Krivelevich, Fast embedding of spanning trees in biased Maker-Breaker games.
    European Journal of Combinatorics 33 (2012), 1086-1099.  
  • I. Ben-Eliezer, M. Krivelevich and B. Sudakov, The size Ramsey number of a directed path.
    Journal of Combinatorial Theory Series B 102 (2012), 743-755.  
  • I. Ben-Eliezer, M. Krivelevich and B. Sudakov, Biased orientation games.
    Discrete Mathematics 312 (2012), 1732-1742.  
  • A. Frieze, M. Krivelevich and P.-S. Loh, Variations on cops and robbers.
    Journal of Graph Theory 69 (2012), 383-402.  
  • M. Krivelevich and R. Spohel, Creating small subgraphs in Achlioptas processes with growing parameter.
    SIAM Journal on Discrete Mathematics 26 (2012), 670-686.  
  • A. Frieze and M. Krivelevich, Packing Hamilton cycles in random and pseudo-random hypergraphs.
    Random Structures and Algorithms 41 (2012), 1-22.  
  • I. Ben-Eliezer, M. Krivelevich and B. Sudakov, Long cycles in subgraphs of (pseudo)random directed graphs.
    Journal of Graph Theory 70 (2012), 284-296.  
  • M. Krivelevich and W. Samotij, Optimal packings of Hamilton cycles in sparse random graphs.
    SIAM Journal on Discrete Mathematics 26 (2012), 964-982.  
  • D. Clemens, A. Ferber, M. Krivelevich and A. Liebenau, Fast strategies in Maker-Breaker games played on random boards.
    Combinatorics, Probability and Computing 21 (2012), 897-915.  
  • D. Hefetz, M. Krivelevich and T. Szabo, Sharp threshold for the appearance of certain spanning trees in random graphs.
    Random Structures and Algorithms 41 (2012), 391-412.  

    TOP
    2013

  • R. Glebov and M. Krivelevich, On the number of Hamilton cycles in sparse random graphs.
    SIAM Journal on Discrete Mathematics 27 (2013), 27-42.  
  • A. Ferber, R. Glebov, M. Krivelevich, H. Liu, C. Palmer, T. Valla and M. Vizer, The biased odd cycle game.
    Electronic Journal of Combinatorics Vol. 20, Issue 2 (2013), publ. P9.  
  • M. Krivelevich, E. Lubetzky and B. Sudakov, Longest cycles in sparse random digraphs.
    Random Structures and Algorithms 43 (2013), 1-15.  
  • M. Krivelevich and B. Sudakov, The phase transition in random graphs - a simple proof.
    Random Structures and Algorithms 43 (2013), 131-138.  
  • A. Frieze and M. Krivelevich, On the non-planarity of a random subgraph.
    Combinatorics, Probability and Computing 22 (2013), 722-732.  
  • A. Ferber, M. Krivelevich and A. Naor, Avoider-Enforcer games played on edge disjoint hypergraphs.
    Discrete Mathematics 313 (2013), 2932-2941.  

    TOP
    2014

  • R. Glebov, M. Krivelevich and T. Szabo, On covering expander graphs by Hamilton cycles.
    Random Structures and Algorithms 44 (2014), 183-200.  
  • M. Krivelevich and W. Samotij, Long paths and cycles in random subgraphs of H-free graphs.
    Electronic Journal of Combinatorics 21(1) (2014), P1.30.  
  • M. Krivelevich, C. Lee and B. Sudakov, Robust Hamiltonicity of Dirac graphs.
    Transactions of the American Mathematical Society 366 (2014), 3095-3130.  
  • D. Bal, A. Frieze, M. Krivelevich and P.-S. Loh, Packing tree factors in random and pseudo-random graphs.
    Electronic Journal of Combinatorics 21(2) (2014), P2.8.  
  • M. Krivelevich, E. Lubetzky and B. Sudakov, Cores of random graphs are born Hamiltonian.
    Proceedings of the London Mathematical Society 109 (2014), 161-188.  
  • M. Krivelevich, Positional games.
    Proceedings of the International Congress of Mathematicians (ICM) 2014, Vol. 4, 355-379.  
  • M. Krivelevich, D. Reichman and W. Samotij, Smoothed analysis on connected graphs.
    Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques (APPROX/RANDOM 2014), LIPICS Vol. 28, 810-825. Journal version: SIAM Journal on Discrete Mathematics 29 (2015), 1654-1669.  
  • A. Ferber, R. Hod, M. Krivelevich and B. Sudakov, A construction of almost Steiner systems.
    Journal of Combinatorial Designs 22 (2014), 488-494.  

    TOP
    2015

  • F. Foucaud, M. Krivelevich and G. Perarnau, Large subgraphs without short cycles.
    SIAM Journal on Discrete Mathematics 29 (2015), 65-78.  
  • A. Coja-Oghlan, U. Feige, M. Krivelevich and D. Reichman, Contagious sets in expanders.
    Proceedings of the 26th Symposium on Discrete Algorithms (SODA'15), 1953-1987. Journal version.  
  • M. Krivelevich, C. Lee and B. Sudakov, Long paths and cycles in random subgraphs of graphs with large minimum degree.
    Random Structures and Algorithms 46 (2015), 320-345.  
  • A. Ferber, R. Glebov, M. Krivelevich and A. Naor, Biased games on random graphs.
    Random Structures and Algorithms 46 (2015), 651-676.  
  • L. Espig, A. Frieze, M. Krivelevich and W. Pegden, Walker-Breaker games.
    SIAM Journal on Discrete Mathematics 29 (2015), 1476-1485.  
  • D. Korandi, M. Krivelevich and B. Sudakov, Decomposing random graphs into cycles and edges.
    Combinatorics, Probability and Computing 24 (2015), 857-872.  
  • M. Krivelevich and G. Kronenberg, Random-player Maker-Breaker games.
    Electronic Journal of Combinatorics 22 (4) (2015), P4.9.  
  • A. Ferber, M. Krivelevich and H. Naves, Generating random graphs in biased Maker-Breaker games.
    Random Structures and Algorithms 47 (2015), 615-634.  

    TOP
    2016

  • D. Hefetz, M. Krivelevich, A. Naor and M. Stojakovic, On saturation games.
    European Journal of Combinatorics 41 (2016), 315-335.  
  • A. Ferber, M. Krivelevich and B. Sudakov, Counting and packing Hamilton l-cycles in dense hypergraphs.
    Journal of Combinatorics 7 (2016), 135-157.  
  • M. Krivelevich, The phase transition in site percolation on pseudo-random graphs.
    Electronic Journal of Combinatorics 23 (1) (2016), P1.12.  
  • D. Hefetz, M. Krivelevich and W. E. Tan, Waiter-Client and Client-Waiter planarity, colorability and minor games.
    Discrete Mathematics 339 (2016), 1525-1536.  
  • A. Ferber and M. Krivelevich, Rainbow Hamilton cycles in random graphs and hypergraphs.
    Recent trends in combinatorics, IMA Volumes in Mathematics and its applications, A. Beveridge, J. R. Griggs, L. Hogben, G. Musiker and P. Tetali, Eds., Springer 2016, 167-189.
  • M. Krivelevich, C. Lee and B. Sudakov, Compatible Hamilton cycles in random graphs.
    Random Structures and Algorithms 49 (2016), 533-557.  
  • M. Bednarska-Bzdega, D. Hefetz, M. Krivelevich and T. Luczak, Manipulative waiters with probabilistic intuition.
    Combinatorics, Probability and Computing 25 (2016), 823-849.  
  • M. Krivelevich, M. Kwan and B. Sudakov, Cycles and matchings in randomly perturbed digraphs and hypergraphs.
    Combinatorics, Probability and Computing 25 (2016), 909-927.  
  • N. Kamcev, M. Krivelevich and B. Sudakov, Some remarks on rainbow connectivity.
    Journal of Graph Theory 83 (2016), 372-383.  
  • A. Ferber, M. Krivelevich, B. Sudakov and P. Vieira, Finding Hamilton cycles in random graphs with few queries.
    Random Structures and Algorithms 49 (2016), 635-668.  
  • O. Dean and M. Krivelevich, Client-Waiter games on complete and random graphs.
    Electronic Journal of Combinatorics 23 (4) (2016), P4.38.  

    TOP
    2017

  • A. Ferber, M. Krivelevich and B. Sudakov, Counting and packing Hamilton cycles in dense graphs and oriented graphs.
    Journal of Combinatorial Theory Series B 122 (2017), 196-220.  
  • A. Ferber, M. Krivelevich, B. Sudakov and P. Vieira, Finding paths in sparse random graphs requires many queries.
    Random Structures and Algorithms 50 (2017), 71-85.  
  • M. Krivelevich, M. Kwan and B. Sudakov, Bounded-degree spanning trees in randomly perturbed graphs.
    SIAM Journal on Discrete Mathematics 31 (2017), 155-171.  
  • M. Krivelevich and P. Michaeli, Small subgraphs in the trace of a random walk.
    Electronic Journal of Combinatorics 24 (1) (2017), P1.28.  
  • D. Hefetz, M. Krivelevich and W. E. Tan, Waiter-Client and Client-Waiter Hamiltonicity games on random graphs.
    European Journal of Combinatorics 63 (2017), 26-43.  
  • A. Ferber, M. Krivelevich and G. Kronenberg, Efficient winning strategies in random-turn Maker-Breaker games.
    Journal of Graph Theory 85 (2017), 446-465.  
  • M. Krivelevich, C. Lee and B. Sudakov, Compatible Hamilton cycles in Dirac graphs.
    Combinatorica 37 (2017), 697-732.  
  • U. Feige, M. Krivelevich and D. Reichman, Contagious sets in random graphs.
    Annals of Applied Probability 27 (2017), 2675-2697.  

    TOP
    2018

  • M. Bednarska-Bzdega, M. Krivelevich, V. Meszaros and C. Requile, Proper colouring Painter-Builder game.
    Discrete Mathematics 341 (2018), 658-664.  
  • M. Krivelevich, Finding and using expanders in locally sparse graphs.
    SIAM Journal on Discrete Mathematics 32 (2018), 611-623.  
  • A. Frieze, M. Krivelevich, P. Michaeli and R. Peled, On the trace of random walks on random graphs.
    Proceedings of the London Mathematical Society 116 (2018), 847-877.  
  • N. Alon and M. Krivelevich, Clique coloring in dense random graphs.
    Journal of Graph Theory 88 (2018), 428-433.  
  • L. Gishboliner, M. Krivelevich and G. Kronenberg, On MAXCUT in strictly supercritical random graphs, and coloring of random graphs and random tournaments.
    Random Structures and Algorithms 52 (2018), 545-559.  
  • C. Dowden, M. Kang and M. Krivelevich, The genus of the Erdős-Rényi random graph and the fragile genus property.
    Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'2018), LIPICS Vol. 110, 17:1-17:13. Journal version: Random Structures and Algorithms 56 (2020), 97-121.  
  • J. Briggs, A. Frieze, M. Krivelevich, P.-S. Loh and B. Sudakov, Packing Hamilton cycles online.
    Combinatorics, Probability and Computing 27 (2018), 475-495.  
  • L. Espig, A. Frieze and M. Krivelevich, Elegantly colored paths and cycles in edge colored random graphs.
    SIAM Journal on Discrete Mathematics 32 (2018), 1585-1618.  
  • M. Krivelevich, M. Kwan, P.-S. Loh and B. Sudakov, The random k-matching free process.
    Random Structures and Algorithms 53 (2018), 692-716.  

    TOP
    2019

  • M. Krivelevich, Long cycles in locally expanding graphs, with applications.
    Combinatorica 39 (2019), 135-151.  
  • P. Haxell, M. Krivelevich and G. Kronenberg, Goldberg's conjecture is true for random multigraphs.
    Journal of Combinatorial Theory Series B 138 (2019), 314-349.  
  • M. Krivelevich, Expanders - how to find them, and what to find in them.
    In Surveys in Combinatorics 2019, A. Lo et al., Eds., London Mathematical Society Lecture Notes 456 (2019), pp. 115-142.  
  • N. Balashov, R. Cohen, A. Haber, M. Krivelevich and S. Haber, Optimal shattering of complex networks.
    Applied Network Science 4:99 (2019).  

    TOP
    2020

  • O. Ben-Eliezer, L. Gishboliner, D. Hefetz and M. Krivelevich, Very fast construction of bounded degree spanning graphs via the semi-random graph process.
    Proceedings of the 31st Symposium on Discrete Algorithms (SODA'20), 728-737. Journal version: Random Structures and Algorithms 57 (2020), 892-919.  
  • Y. Alon and M. Krivelevich, Random graph's Hamiltonicity is strongly tied to its minimum degree.
    Electronic Journal of Combinatorics Vol. 27 (2020), publ. 1.30.  
  • N. Alon, D. Hefetz, M. Krivelevich and M. Tyomkyn, Edge-statistics on large graphs.
    Combinatorics, Probability and Computing 29 (2020), 163-189.  
  • M. Krivelevich, E. Lubetzky and B. Sudakov, Asymptotics in percolation on high-girth expanders.
    Random Structures and Algorithms 56 (2020), 927-947.  
  • M. Krivelevich, T. Mészáros, P. Michaeli and C. Shikhelman, Greedy maximal independent sets via local limits.
    Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'2020), LIPICS Vol. 159, 20:1-20:19. Journal version: Random Structures and Algorithms 64 (2024), 986-1015.  
  • Y. Alon and M. Krivelevich, Finding a Hamilton cycle fast on average using rotations and extensions.
    Random Structures and Algorithms 57 (2020), 32-46.  
  • N. Kamčev, M. Krivelevich, N. Morrison and B. Sudakov, The Kőnig graph process.
    Random Structures and Algorithms 57 (2020), 1272-1302.  

    TOP
    2021

  • N. Draganić, M. Krivelevich and R. Nenadov, Rolling backwards can move you forward: on embedding problems in sparse expanders.
    Proceedings of the 32nd Symposium on Discrete Algorithms (SODA'21), 123-134. Journal version: Transactions of the American Mathematical Society 375 (2022), 5195-5216.  
  • L. Friedman and M. Krivelevich, Cycle lengths in expanding graphs.
    Combinatorica 41 (2021), 53-74.  
  • N. Draganić, M. Krivelevich and R. Nenadov, The size-Ramsey number of short subdivisions.
    Random Structures and Algorithms 59 (2021), 68-78.  
  • J. Erde, M. Kang and M. Krivelevich, Large complete minors in random subgraphs.
    Combinatorics, Probability and Computing 30 (2021), 619-630.  
  • M. Krivelevich and R. Nenadov, Complete minors in graphs without sparse cuts.
    International Mathematics Research Notices 2021, No. 12, pp. 8996-9015.  
  • N. Alon and M. Krivelevich, Divisible subdivisions.
    Journal of Graph Theory 98 (2021), 623-629.  

    TOP
    2022

  • L. Gishboliner, M. Krivelevich and P. Michaeli, Discrepancies of spanning trees and Hamilton cycles.
    Journal of Combinatorial Theory Series B 154 (2022), 262-291.  
  • L. Gishboliner, M. Krivelevich and P. Michaeli, Colour-biased Hamilton cycles in random graphs.
    Random Structures and Algorithms 60 (2022), 289-307.  
  • Y. Alon and M. Krivelevich, Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs.
    SIAM Journal on Discrete Mathematics 36 (2022), 728-754.  
  • A. Ferber and M. Krivelevich, Every graph contains a linearly sized induced subgraph with all degrees odd.
    Advances in Mathematics 406 (2022), 108534.  
  • Y. Alon, M. Krivelevich and P. Michaeli, Spanning trees at the connectivity threshold.
    SIAM Journal on Discrete Mathematics 36 (2022), 1612-1626.  
  • Y. Alon, M. Krivelevich and E. Lubetzky, Cycle lengths in sparse random graphs.
    Random Structures and Algorithms 61 (2022), 444-461.  
  • N. Draganić, S. Glock and M. Krivelevich, Short proofs for long induced paths.
    Combinatorics, Probability and Computing 31 (2022), 870-878.  
  • S. Diskin and M. Krivelevich, On the performance of the Depth First Search algorithm in supercritical random graphs.
    Electronic Journal of Combinatorics 29 (2022), P3.64  
  • N. Draganić, S. Glock and M. Krivelevich, The largest hole in sparse random graphs.
    Random Structures and Algorithms 61 (2022), 666-677.  
  • R. Hod, M. Krivelevich, T. Müller, A. Naor and N. Wormald, Component games on random graphs.
    Combinatorica 42 (2022), 1189-1229.  

    TOP
    2023

  • J. Erde, M. Kang and M. Krivelevich, Expansion in supercritical random subgraphs of the hypercube and its consequences
    Annals of Probability 51 (2023), 127-156.  
  • M. Krivelevich, G. Kronenberg and A. Mond, Turán-type problems for long cycles in random and pseudo-random graphs.
    Journal of the London Mathematical Society 107 (2023), 1519-1551.  
  • S. Diskin and M. Krivelevich, Supercritical site percolation on the hypercube: small components are small.
    Combinatorics, Probability and Computing 32 (2023), 422-427.  
  • N. Alon, M. Krivelevich and W. Samotij, Largest subgraph from a hereditary property in a random graph.
    Discrete Mathematics 346 (2023), 113480.  
  • N. Alon, M. Krivelevich and B. Sudakov, Complete minors and average degree - a short proof.
    Journal of Graph Theory 103 (2023), 599-602.  
  • L. Gishboliner, M. Krivelevich and P. Michaeli, Oriented discrepancy of Hamilton cycles.
    Journal of Graph Theory 103 (2023), 780-792.  
  • A. Ferber, L. Hardiman and M. Krivelevich, On subgraphs with degrees of prescribed residues in the random graph.
    Random Structures and Algorithms 63 (2023), 192-214.  
  • S. Diskin and M. Krivelevich, Site percolation on pseudo-random graphs.
    Random Structures and Algorithms 63 (2023), 406-441.  
  • E. Aigner-Horev, D. Hefetz and M. Krivelevich, Cycle lengths in randomly perturbed graphs.
    Random Structures and Algorithms 63 (2023), 867-884.  

    TOP
    2024

  • S. Diskin, I. Hoshen, M. Krivelevich and M. Zhukovskii, On vertex Ramsey graphs with forbidden subgraphs.
    Discrete Mathematics 347 (2024), 113806.  
  • Y. Alon and M. Krivelevich, Hamilton completion and the path cover number of sparse random graphs.
    European Journal of Combinatorics 118 (2024), 103934.  
  • S. Diskin, J. Erde, M. Kang and M. Krivelevich, Percolation on irregular high-dimensional product graphs.
    Combinatorics, Probability and Computing 33 (2024), 377-403.  
  • S. Diskin, J. Erde, M. Kang and M. Krivelevich, Isoperimetric inequalities and supercritical percolation on high-dimensional product graphs.
    Combinatorica 44 (2024), 741–784.  
  • S. Diskin and M. Krivelevich, Expansion in supercritical random subgraphs of expanders and its consequences.
    Random Structures and Algorithms 65 (2024), 576-600.  
  • M. Krivelevich and M. Zhukovskii, Maximum chordal subgraphs of random graphs.
    Combinatorics, Probability and Computing 33 (2024), 611-623.  

    TOP
    Preprints

  • D. Hefetz, M. Krivelevich, M. Stojakovic and T. Szabo, Continuous Box game.  
  • M. Krivelevich, Long paths and Hamiltonicity in random graphs.  
  • M. Krivelevich and N. Trumer, Waiter-Client maximum degree game.  
  • J. Erde, M. Kang and M. Krivelevich, Expansion, long cycles and complete minors in supercritical random subgraphs of the hypercube.  
  • M. Krivelevich, The choosability version of Brooks' theorem - a short proof.  
  • A. Frieze, M. Krivelevich and P. Michaeli, Fast construction on a restricted budget.  
  • S. Diskin, J. Erde, M. Kang and M. Krivelevich, Percolation on high-dimensional product graphs.  
  • E. Aigner-Horev, D. Hefetz and M. Krivelevich, Minors, connectivity, and diameter in randomly perturbed sparse graphs.  
  • M. Krivelevich, Crowns in pseudo-random graphs and Hamilton cycles in their squares.  
  • Y. Alon and M. Krivelevich, Sparse pancyclic subgraphs of random graphs.  
  • S. Diskin, J. Erde, M. Kang and M. Krivelevich, Percolation through isoperimetry.  
  • N. Alon, M. Bucić, M. Christoph and M. Krivelevich, The power of many colours.  
  • M. Krivelevich, Component sizes in the supercritical percolation on the binary cube.  
  • M. Krivelevich, A. Lew and P. Michaeli, Rigid partitions: from high connectivity to random graphs.  
  • M. Anastos, S. Diskin, D. Elboim and M. Krivelevich, Climbing up a random subgraph of the hypercube.  
  • D. Hefetz and M. Krivelevich, Colouring graphs from random lists.  
  • S. Diskin and M. Krivelevich, Hitting time of connectedness in the random hypercube process  
  • M. Krivelevich and M. Zhukovskii, Reconstructing random graphs from distance queries.  
  • B. Bukh, M. Krivelevich and B. Narayanan, Colouring random subgraphs.  
  • M. Collares, S. Diskin, J. Erde and M. Krivelevich, Long cycles in percolated expanders.  
  • S. Diskin, J. Erde, M. Kang and M. Krivelevich, Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs.  
  • S. Diskin and M. Krivelevich, Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree  
  • S. Diskin and M. Krivelevich, Components, large and small, are as they should be II: supercritical percolation on regular graphs of constant degree  
  • N. Draganić and M. Krivelevich, Disjoint connected dominating sets in pseudorandom graphs.