The burning number conjecture states that the burning number of a connected graph is at most $\lceil \sqrt{ n} \rceil.$ While the conjecture is unresolved, Land and Lu proved that the burning number of a connected graph is at most $ \sqrt{ (3/2)n}+O(1).$ Using an algorithmic approach, we provide an improved upper bound for the burning number of a connected graph: $$\bigg \lceil \frac{ \sqrt{ 12n+64}+8}{ 3} \bigg \rceil = \sqrt{ (4/3)n} +O(1) .$$

Categories: math.CO

An improved bound on the burning number of graphs