2021/10/20 by Bastide, Paul, Bonamy, Marthe, Bonato, Anthony +4 · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2110.10530
The Burning Number Conjecture claims that for every connected graph G of order n, its burning number satisfies b(G) ≤ \lceil √(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) ≤ √(4n/3) + 1, improving on the previously known √(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.