The Burning Graph Conjecture for trees

Let TT be a tree on nn vertices. For a set BNB\subseteq\mathbb{N}, say that TT is BB-burnable if there is a sequence of vertices X={v1,,vj}X=\{v_1,\ldots,v_j\} such that

i{1,,j}Nbi[vi]=V(T),\bigcup_{i\in\{1,\ldots,j\}}N_{b_i}[v_i]=V(T),

where B={b1,,bj}B=\{b_1,\ldots,b_j\}. Here Nr[v]N_r[v] denotes the closed radius-rr neighborhood of vv.

Burning Graph Conjecture. Every tree TT on nn vertices is {0,,n1}\{0,\ldots,\lceil\sqrt{n}\rceil-1\}-burnable.

This is the tree formulation of the general burning conjecture. It remains open in general, while the paper proves reductions for trees of bounded growth and establishes improved approximate bounds.

Sources & referencesView supporting material

Primary source

Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, Shahin Kamali, Théo Pierron and Mikaël Rabie, “Improved pyrotechnics : Closer to the burning graph conjecture”, arXiv:2110.10530 (2022).

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.