The Burning Number Conjecture Holds Asymptotically
The burning number b(G) of a graph G is the smallest number of turns required to burn all vertices of a graph if at every turn a new fire is started and existing fires spread to all adjacent vertices. The Burning Number Conjecture of Bonato et al. (2016) postulates that b(G)≤⌈√(n)⌉ for all graphs G on n vertices. We prove that this conjecture holds asymptotically, that is b(G)≤ (1+o(1))√(n).
READ FULL TEXT