摘要
Let alpha(1)(G) denote the maximum size of an edge set that contains at most one edge from each triangle of G. Let tau(B)(G) denote the minimum size of an edge set whose deletion makes G bipartite. It was first conjectured by Lehel and later independently by Puleo that alpha(1)(G) + tau(B)(G) <= n(2)/4 for every n-vertex graph G. Puleo showed that alpha(1)(G) + tau(B)(G) <= 5n(2)/16 for every n-vertex graph G. In this note, we improve the bound by showing that alpha(1)(G) tau(B)(G) <= 4403n(2)/15000 for every n-vertex graph G.
- 出版日期2017-2-6