Journal of Combinatorics
Volume 12 (2021)
Zero-forcing in random regular graphs
Pages: 85 – 116
The zero-forcing process is an iterative graph colouring process in which at each time step a coloured vertex with a single uncoloured neighbour can force this neighbour to become coloured. A zero-forcing set of a graph is an initial set of coloured vertices that can eventually force the entire graph to be coloured. The zero-forcing number is the size of the smallest zero-forcing set. We explore the zero-forcing number for random regular graphs, improving on bounds given by Kalinowski, Kamčev and Sudakov . We also propose and analyze a degree-greedy algorithm for finding small zero-forcing sets using the differential equations method.
zero-forcing number, random regular graphs, random graphs, DE method, expanders
Patrick Bennett was supported in part by Simons Foundation Grant #426894.
Calum MacRury and Paweł Prałat were supported in part by the Natural Sciences and Engineering Research Council.
Received 5 January 2019
Accepted 19 March 2020
Published 4 January 2021