Geodesic
Improved pyrotechnics: closer to the burning number conjecture
Paul Bastide1 ; Marthe Bonamy2 ; Anthony Bonato3 ; Pierre Charbit4 ; Shahin Kamali5 ; Théo Pierron6 ; Mikaël Rabie4
1ENS Rennes - LaBri
2CNRS, LaBRI, Université de Bordeaux
3Ryerson University, Toronto
4IRIF, Paris
5University of Manitoba, Winnipeg
6LIRIS, Université de Lyon, Lyon
The electronic journal of combinatorics, Tome 30 (2023) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The Burning Number Conjecture claims that for every connected graph $G$ of order $n,$ its burning number satisfies $b(G) \le \lceil \sqrt{n}\, \rceil.$ While the conjecture remains open, we prove that it is asymptotically true when the order of the graph is much larger than its growth, which is the maximal distance of a vertex to a well-chosen path in the graph. We prove that the conjecture for graphs of bounded growth reduces to a finite number of cases. We provide the best-known bound on the burning number of a connected graph $G$ of order $n,$ given by $b(G) \le \sqrt{4n/3} + 1,$ improving on the previously known $\sqrt{3n/2}+O(1)$ bound. Using the improved upper bound, we show that the conjecture almost holds for all graphs with minimum degree at least $3$ and holds for all large enough graphs with minimum degree at least $4$. The previous best-known result was for graphs with minimum degree $23$.
DOI : 10.37236/11113
Classification : 05C85, 05C40, 05C12
Mots-clés : burning number conjecture, burning number of a connected graph

Paul Bastide  1   ; Marthe Bonamy  2   ; Anthony Bonato  3   ; Pierre Charbit  4   ; Shahin Kamali  5   ; Théo Pierron  6   ; Mikaël Rabie  4

1 ENS Rennes - LaBri
2 CNRS, LaBRI, Université de Bordeaux
3 Ryerson University, Toronto
4 IRIF, Paris
5 University of Manitoba, Winnipeg
6 LIRIS, Université de Lyon, Lyon 
@article{10_37236_11113,
     author = {Paul Bastide and Marthe Bonamy and Anthony Bonato and Pierre Charbit and Shahin  Kamali and Th\'eo  Pierron and Mika\"el  Rabie},
     title = {Improved pyrotechnics: closer to the burning number conjecture},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {4},
     doi = {10.37236/11113},
     zbl = {1532.05156},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11113/}
}
TY  - JOUR
AU  - Paul Bastide
AU  - Marthe Bonamy
AU  - Anthony Bonato
AU  - Pierre Charbit
AU  - Shahin  Kamali
AU  - Théo  Pierron
AU  - Mikaël  Rabie
TI  - Improved pyrotechnics: closer to the burning number conjecture
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11113/
DO  - 10.37236/11113
ID  - 10_37236_11113
ER  - 
%0 Journal Article
%A Paul Bastide
%A Marthe Bonamy
%A Anthony Bonato
%A Pierre Charbit
%A Shahin  Kamali
%A Théo  Pierron
%A Mikaël  Rabie
%T Improved pyrotechnics: closer to the burning number conjecture
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/11113/
%R 10.37236/11113
%F 10_37236_11113
Paul Bastide; Marthe Bonamy; Anthony Bonato; Pierre Charbit; Shahin  Kamali; Théo  Pierron; Mikaël  Rabie. Improved pyrotechnics: closer to the burning number conjecture. The electronic journal of combinatorics, Tome 30 (2023) no. 4. doi: 10.37236/11113

Cité par Sources :