Erratum: The 2‐surviving rate of planar graphs with average degree lower than 92
Przemysław Gordinowicz · Journal of Graph Theory · 2021
In this note the correction to the proof of Theorem 1.2 from Gordinowicz and the corrected version of Corollary 1.4 is presented. In [1] the firefighter problem on planar graphs was considered. In particular the following bound for the 2-surviving rate (expected fraction of the vertices of a graph saved from the fire starting at a random vertex, provided that two vertices per round can be protected) was established. Theorem 1.2.Let G be any connected planar graph with n ≥ 2 vertices and m edges. If for some ϵ ∈ ( 0 , 5 2 ] one has 2 m n = 9 2 − ϵ, then However, as pointed out by Bartosz Walczak, there was some technical/calculation error in the proof (the solution of an auxiliary parameterised linear program was partially incorrect) which caused a gap in the proof for graphs on less than 36 vertices. A complete, corrected proof is presented in Section 2. We note that Theorem 1.2 remains unchanged. The theorem was followed by two corollaries and one of them also needs a correction. There was some miscalculation (again pointed out by Bartosz Walczak) in the bound for average degree for planar graphs without 4-cycles. The proper value is 30 7 (one can either check it in, e.g., [3, Lemma 1.7] or derive it directly from Euler Formula) and it leads to the following. Corollary 1.4. ((Corrected))Let G be any graph on at least two vertices. If G does not contain any 4-cycle, then We refer the reader to the original paper for the definitions and notations used in this note. The numbering of theorems, lemmas and corollaries follows the numeration in [1]. The solution is the following (see [2] for calculations done for this paper, in particular for solutions of all linear programs). In each case α ≥ 2 9 ε − 1 n . Moreover, in Cases 2 and 4 (for ε ∈ ( 0 , 9 8 ] ) one has α ≥ 2 9 ε. For the first case note that ρ 2 ( G ) can be easily bounded directly: protecting two vertices in the first round firefighters protects at least 2 17 > 2 9 ε vertices of the graph, no matter where the fire starts. For Case 3 and for ε ∈ ( 1 2 , 1 ] at first note that 1 6 ε ( 1 + 1 n ) + 1 12 − 11 12 n ≥ 2 9 ε for n ≥ 27. Then, notice that protecting two vertices at the first step is enough to obtain the bound ρ 2 ( G ) ≥ 2 9 ε for n ≤ 9. The author would like to thank Bartosz Walczak for his careful reading of [1] and for pointing out the errors.