# Planar graph is on fire

• Published in 2015
In the collections
Let $G$ be any connected graph on $n$ vertices, $n \ge 2.$ Let $k$ be any positive integer. Suppose that a fire breaks out on some vertex of $G.$ Then in each turn $k$ firefighters can protect vertices of $G$ --- each can protect one vertex not yet on fire; Next a fire spreads to all unprotected neighbours. The $\$emph{$k$-surviving} rate of G, denoted by $\rho_k(G),$ is the expected fraction of vertices that can be saved from the fire by $k$ firefighters, provided that the starting vertex is chosen uniformly at random. In this paper, it is shown that for any planar graph $G$ we have $\rho_3(G) \ge \frac{2}{21}.$ Moreover, 3 firefighters are needed for the first step only; after that it is enough to have 2 firefighters per each round. This result significantly improves known solutions to a problem of Cai and Wang (there was no positive bound known for surviving rate of general planar graph with only 3 firefighters). The proof is done using the separator theorem for planar graphs.

## Other information

issn
03043975
journal
Theoretical Computer Science
pages
160--164
volume
593

### BibTeX entry

@article{Gordinowicz2015,
abstract = {Let {\$}G{\$} be any connected graph on {\$}n{\$} vertices, {\$}n \ge 2.{\$} Let {\$}k{\$} be any positive integer. Suppose that a fire breaks out on some vertex of {\$}G.{\$} Then in each turn {\$}k{\$} firefighters can protect vertices of {\$}G{\$} --- each can protect one vertex not yet on fire; Next a fire spreads to all unprotected neighbours.   The {\$}\{\$}emph{\{}{\$}k{\$}-surviving{\}} rate of G, denoted by {\$}\rho{\_}k(G),{\$} is the expected fraction of vertices that can be saved from the fire by {\$}k{\$} firefighters, provided that the starting vertex is chosen uniformly at random. In this paper, it is shown that for any planar graph {\$}G{\$} we have {\$}\rho{\_}3(G) \ge \frac{\{}2{\}}{\{}21{\}}.{\$} Moreover, 3 firefighters are needed for the first step only; after that it is enough to have 2 firefighters per each round. This result significantly improves known solutions to a problem of Cai and Wang (there was no positive bound known for surviving rate of general planar graph with only 3 firefighters). The proof is done using the separator theorem for planar graphs.},
author = {Gordinowicz, Przemys{\l}aw},
issn = 03043975,
journal = {Theoretical Computer Science},
month = {aug},
pages = {160--164},
title = {Planar graph is on fire},
url = {http://arxiv.org/abs/1311.1158 http://arxiv.org/pdf/1311.1158v2},
volume = 593,
year = 2015,
archivePrefix = {arXiv},
eprint = {1311.1158},
primaryClass = {math.CO},
urldate = {2015-12-02},
collections = {Attention-grabbing titles,Puzzles,Fun maths facts}
}