The Burning Graph Conjecture for trees

About 5 years old · traced to

Let TT be a tree on nn vertices. For a set B⊆NB\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,…,⌈n⌉−1}\{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.

References

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.