← All problems

Burning Number Conjecture for connected graphs

7 years old · traced to

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

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

This conjecture proposes a sharp upper bound for graph burning, improving the previously known bound b(G)≤2⌈n⌉−1b(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. Let GG be a connected graph of order nn, and let b(G)b(G) denote its burning number.

    Burning number conjecture.

    b(G)≤⌈n⌉.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).

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.

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

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.

Solutions 0

No solutions have been posted yet.