hide
Free keywords:
-
Abstract:
We show that any face hitting set of size n of a connected planar graph with a
minimum degree of at least 3 is contained in a connected subgraph of size 5n−6.
Furthermore we show that this bound is tight by providing a lower bound in the
form of a family of graphs. This improves the previously known upper and lower
bound of 11n−18 and 3n respectively by Grigoriev and Sitters. Our proof is
valid for simple graphs with loops and generalizes to graphs embedded in
surfaces of arbitrary genus.
