Bonato et al. (2014, 2015) defined the burning number of a finite, simple, undirected graph as follows. Consider a process called burning involving are discrete
time steps. Each node is either burned or unburned; if a node is burned, then it
remains in that state until the end of the process. In every round, choose one additional
unburned node to burn (if such a node is available). Once a node is burned in round
, in round , each of its unburned neighbors becomes burned. The process
ends when all nodes are burned. The burning number of a graph , written by (Bonato et al. 2014) or (Gautam et al. 2020), is then defined as the minimum
number of rounds needed for the process to end.

The decision version of the graph burning problem is NP-complete (Bessy et al. 2017). The burning number problem on disconnected
graphs is harder than on connected graphs
(Gautam et al. 2021). This is because in a disconnected graph, you can start
fires in the larger connected components early and let those fires propagate on their
own while fires setting on smaller components.

By construction, the burning number satisfies

(1)

where
is the cooling number. This is because burning
number corresponds to the first iteration in which a completely burnt graph first
occurs, while the cooling number corresponds to
the iteration in which no partially-uncooled graph remains.

and conjecture that this inequality holds for any connected graph. Bonato (2020) calls this statement the "burning number conjecture,"
and terms any graph that satisfies the inequality "well-burnable." The
best known upper bound is given by

Bessy, S.; Bonato, A.; Jansen, J.; Rautenbach, D.; and Roshanbin, E. "Bounds on the Burning Number." 2 Nov 2016. https://arxiv.org/abs/1511.06023.Bessy,
S.; Bonato, A.; Jansen, J.; Rautenbach, D. R.; and Roshanbin, E. "Burning
a Graph Is Hard." Disc. Appl. Math.232, 73-87, 2017.Bonato,
S. "A Survey of Graph Burning." 22 Sep 2020. https://arxiv.org/abs/2009.10642v1.Bonato,
A.; Janssen, J.; and Roshanbin, E. "Burning a Graph as a Model of Social Contagion."
In Algorithms
and Models for the Web Graph: 11th International Workshop, WAW 2014, Beijing, China,
December 17-18, 2014, Proceedings (Ed. A. Bonato A., F. Graham
F., and P. Prałat). Springer, pp. 13-22, 2014.Bonato,
A.; Janssen, J.; and Roshanbin, E. "How to Burn a Graph." To appear in
Internet Mathematics. 23 Jul 2015. https://arxiv.org/abs/1507.06524.Bonato,
A.; Marbach, T. G.; Milne, H.; and Mishura, T. "How to Cool a Graph."
https://arxiv.org/abs/2401.03496.
7 Jan 2024.Gautam, R. K.; Kare, A. S.; and Bhavani, S. D.
"Faster Heuristics for Graph Burning." Appl. Intelligence52,
1351-1361, 2021.Land, M. and Lu, L. "An Upper Bound on Burning
Number of Graphs." In Proceedings of WAW'16. 2016.