|کد مقاله||کد نشریه||سال انتشار||مقاله انگلیسی||ترجمه فارسی||نسخه تمام متن|
|4646551||1413648||2017||8 صفحه PDF||سفارش دهید||دانلود کنید|
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.
Journal: Discrete Mathematics - Volume 340, Issue 2, 6 February 2017, Pages 23–30