A note on bipartite subgraphs and triangle-independent sets

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.