Let G be a connected graph on n vertices, and let b(G) denote the minimum number of rounds needed to burn all vertices of G. Burning Number Conjecture. b(G) ≤ lceil√nrceil. This conjecture proposes a sharp upper bound for graph burning, improving the previously known bound b(G)≤ 2 lceil√nrceil-1 and one attained by paths. It remains a central open problem in the area.

Burning Number Conjecture for connected graphs

Let $G$ be a connected graph on $n$ vertices, and let $b(G)$ denote the minimum number of rounds needed to burn all vertices of $G$ . Burning Number Conjecture.

b(G) \leq \lceil\sqrt{n}\rceil.

This conjecture proposes a sharp upper bound for graph burning, improving the previously known bound $b(G)\leq 2\lceil\sqrt{n}\rceil-1$ and one attained by paths. It remains a central open problem in the area.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

The burning number conjecture for connected graphs
Let $G$ be a connected graph of order $n$ , and let $b(G)$ denote its burning number.

Burning number conjecture.
$b(G) \leq \lceil\sqrt{n}\rceil.$
The conjecture is a central open problem in graph burning. While the full conjecture has so far remained unresolved, it is known to hold for special classes of graphs.
source: Jean Guillaume and Tyriana Williams, “A Structural Approach to Burning Number”, arXiv:2606.04178 (2026).

Sources & referencesView supporting material

Primary source

Jesper Jansson, Shashanka Kulamarva, Yukihiro Murakami and Nikolaas Verhulst, “Burning Graph Powers and Branching Trees”, arXiv:2604.23004 (2026).

Additional references

3 papers in this index state this conjecture (2019–2026). The statement above is taken from the most recent of them; the others are arXiv:2207.04035, arXiv:1912.10897.

graph-burning graph-theory

1 week ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

No solutions have been posted yet.

Equivalent formulations 1

The burning number conjecture for connected graphs

Primary source

Additional references

Progress summary