کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4646551 1413648 2017 8 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 340, Issue 2, 6 February 2017, Pages 23–30
نویسندگان
,