Packing and covering odd cycles in cubic plane graphs with small faces

Abstract

We show that any $3$-connected cubic plane graph on $n$ vertices, with all faces of size at most $6$, can be made bipartite by deleting no more than $\sqrt{(p+3t)n/5}$ edges, where $p$ and $t$ are the numbers of pentagonal and triangular faces, respectively. In particular, any such graph can be made bipartite by deleting at most $\sqrt{12n/5}$ edges. This bound is tight, and we characterise the extremal graphs. We deduce tight lower bounds on the size of a maximum cut and a maximum independent set for this class of graphs. This extends and sharpens the results of Faria, Klein and Stehlik [SIAM J. Discrete Math. 26 (2012) 1458-1469].

16 pages; to appear in European J. Combin.; an extended abstract of this paper appeared in the proceedings of EuroComb 2017

References in corpus (2)

• Odd cycle transversals and independent sets in fullerene graphs
• Shapes of polyhedra and triangulations of the sphere