Article ID Journal Published Year Pages File Type
4646551 Discrete Mathematics 2017 8 Pages PDF
Abstract

Let α1(G)α1(G) denote the maximum size of an edge set that contains at most one edge from each triangle of GG. Let τB(G)τB(G) denote the minimum size of an edge set whose deletion makes GG bipartite. It was first conjectured by Lehel and later independently by Puleo that α1(G)+τB(G)≤n2∕4α1(G)+τB(G)≤n2∕4 for every nn-vertex graph GG. Puleo showed that α1(G)+τB(G)≤5n2∕16α1(G)+τB(G)≤5n2∕16 for every nn-vertex graph GG. In this note, we improve the bound by showing that α1(G)+τB(G)≤4403n2∕15000α1(G)+τB(G)≤4403n2∕15000 for every nn-vertex graph GG.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,