Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777342 | European Journal of Combinatorics | 2018 | 14 Pages |
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 (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 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 et al. (2012).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Diego Nicodemos, MatÄj StehlÃk,