# Planar graph is on fire

- Published in 2015
- Added on

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.

## Links

## 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} }