Xavier Pérez Giménez

(Back to homepage)

Publications

(co-authors who are undergraduate students are marked in red.)
  1. The chromatic number of random lifts of complete graphs (preprint)
    (with JD Nir)
    Preprint, 62 pp.

  2. Rainbow Hamilton cycles in random geometric graphs (preprint)
    (with A. Frieze)
    Submitted, 19 pp.

  3. The phase transition of discrepancy in random hypergraphs (preprint)
    (with C. MacRury, T. Masařík and L. Pai)
    Submitted, 20 pp.

  4. On-line size Ramsey number for monotone k-uniform ordered paths with uniform looseness (preprint) (doi)
    (with P. Prałat and D. West)
    European Journal of Combinatorics, 92, 103242, 14 pp., 2021.

  5. On the existence of Hamilton cycles with a periodic pattern in a random digraph (preprint) (doi)
    (with A. Frieze and P. Prałat)
    The Electronic Journal of Combinatorics, 27(4), #P4.30, 2020.

  6. Perfect matchings and Hamiltonian cycles in the preferential attachment model (preprint) (doi)
    (with A. Frieze, P. Prałat and B. Reiniger)
    Random Structures & Algorithms, 54(2):258-288, 2019.

  7. The game of Overprescribed Cops and Robbers played on graphs (doi)
    (with A. Bonato, P. Prałat and B. Reiniger)
    Graphs and Combinatorics, 33(4):801-815, 2017.

  8. Randomly Twisted Hypercubes (doi)
    (with A. Dudek, P. Prałat, H. Qi, D. West and X. Zhu)
    European Journal of Combinatorics, 70:364-373, 2018.

  9. Subhypergraphs in non-uniform random hypergraphs (doi)
    (with M. Dewar, J. Healy, P. Prałat, J. Proos, B. Reiniger and K. Ternovsky)
    Internet Mathematics, 23 pp., 2018.

    Conference version:
    Subgraphs in non-uniform random hypergraphs
    In 13th Workshop on Algorithms and Models for the Web Graph (WAW), 2016.

  10. Rainbow perfect matchings and Hamilton cycles in the random geometric graph (preprint) (doi)
    (with D. Bal, P. Bennett and P. Prałat)
    Random Structures & Algorithms, 51(4):587-606, 2017.

  11. Injective colouring of binomial random graphs (preprint)
    (with R.M. del Río-Chanona, C. MacRury, J. Nicolaidis, P. Prałat and K. Ternovsky)
    Unpublished manuscript, 11 pp.

  12. The robot crawler graph process (doi)
    (with A. Bonato, R.M. del Río-Chanona, C. MacRury, J. Nicolaidis, P. Prałat and K. Ternovsky)
    Discrete Applied Mathematics, 247:23-36, 2018.

    Conference version:
    The robot crawler number of a graph
    In 12th Workshop on Algorithms and Models for the Web-graph (WAW), 2015.

  13. Arboricity and spanning-tree packing in random graphs (preprint) (doi)
    (with P. Gao and C.M. Sato)
    Random Structures & Algorithms, 52(3):495-535, 2018.

    Conference version:
    Arboricity and spanning-tree packing in random graphs with an application to load balancing
    In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

  14. Strong-majority bootstrap percolation on regular graphs with low dissemination threshold (preprint) (doi)
    (with D. Mitsche and P. Prałat)
    Stochastic Processes and their Applications, 127(9):3110-3134, 2017.

  15. A probabilistic version of the game of zombies and survivors on graphs (doi)
    (with A. Bonato, D. Mitsche and P. Prałat)
    Theoretical Computer Science, 655(A):2-14, 2016.

  16. On the relation between graph distance and Euclidean distance in random geometric graphs. (preprint) (doi)
    (with J. Díaz, D. Mitsche and G. Perarnau)
    Advances in Applied Probability, 48(3):848-864, 2016.

  17. The bondage number of random graphs (preprint) (doi)
    (with D. Mitsche and P. Prałat)
    The Electronic Journal of Combinatorics, 23(2), #P2.13, 2016.

  18. On-line list colouring of random graphs (preprint) (doi)
    (with A. Frieze, D. Mitsche and P. Prałat)
    The Electronic Journal of Combinatorics, 22(2), #P2.41, 2015.

  19. The domination number of on-line social networks
    (with A. Bonato, M. Lozier, D. Mitsche and P. Prałat)
    In 12th Annual Conference on Theory and Applications of Models of Computation (TAMC), 2015.

  20. Randomized Rumor Spreading: the Effect of the Network Topology (preprint) (doi)
    (with K. Panagiotou, T. Sauerwald and H. Sun)
    Combinatorics, Probability and Computing, 24(2):457–479, 2015.

  21. Asymptotic enumeration of strongly connected digraphs by vertices and edges (preprint) (doi)
    (with N. Wormald)
    Random Structures & Algorithms, 43(1):80-114, 2013.

  22. Disjoint Hamilton cycles in the random geometric graph (preprint) (doi)
    (with T. Müller and N. Wormald)
    Journal of Graph Theory, 68(4):299-322, 2011.

  23. On the chromatic number of random d-regular graphs (preprint) (doi)
    (with G. Kemkes and N. Wormald)
    Advances in Mathematics, 223(1):300-328, 2010.

  24. On the satisfiability threshold of formulas with three literals per clause (doi)
    (with J. Díaz, L. Kirousis and D. Mitsche)
    Theoretical Computer Science, 410(30-32):2920-2934, 2009.

    Conference version:
    A new upper bound for 3-SAT
    In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2008.

  25. Large connectivity for dynamic random geometric graphs (doi)
    (with J. Díaz and D. Mitsche)
    IEEE Transactions on Mobile Computing, 8(6):821-835, 2009.

    Conference version:
    On the connectivity of dynamic random geometric graphs
    (with J. Díaz and D. Mitsche)
    In 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.

  26. On the probability of the existence of fixed-size components in random geometric graphs (doi)
    (with J. Díaz and D. Mitsche)
    Advances in Applied Probability, 41(2):344-357, 2009.

  27. On the chromatic number of a random 5-regular graph (doi)
    (with J. Díaz, A.C. Kaporis, G.D. Kemkes, L.M. Kirousis and N. Wormald)
    Journal of Graph Theory, 61(3):157-191, 2009.

    Conference (related) version:
    5-regular graphs are 3-colorable with positive probability
    (with J. Díaz, G. Grammatikopoulos, A. Kaporis, L. Kirousis and D. G. Sotiropoulos)
    In 13th Annual European Symposium on Algorithms (ESA), 2005.

    Also:
    Partitioning networks into classes of mutually isolated nodes
    (with J. Díaz, A. Kaporis and L. Kirousis)
    In European Conference on Complex Systems (ECCS), 2005.

  28. Walkers on the cycle and the grid (doi)
    (with J. Díaz, M. J. Serna and N. C. Wormald)
    SIAM Journal on Discrete Mathematics, 22(2):747-775, 2008.

    Conference version:
    Connectivity for wireless agents moving on a cycle or grid
    (with J. Díaz, M. J. Serna and N. C. Wormald)
    In 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2005.

  29. Sharp threshold for hamiltonicity of random geometric graphs (doi)
    (with J. Díaz and D. Mitsche)
    SIAM Journal on Discrete Mathematics, 21(1):57-65, 2007.

  30. Empirical analysis of the connectivity threshold of mobile agents on the grid.
    In 4th International Workshop on Efficient and Experimental Algorithms (WEA), 2005.


  31. Aspects of Random Graphs: colourings, walkers and Hamiltonian cycles.
    Ph.D. Dissertation, 2007.

(Back to homepage)