کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418456 681673 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A lower bound on the independence number of a graph in terms of degrees and local clique sizes
ترجمه فارسی عنوان
اتصال پایین تر بر روی تعداد مستقل یک گراف از نظر درجه و اندازه دسته محلی
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Caro and Wei independently showed that the independence number α(G)α(G) of a graph GG is at least ∑u∈V(G)1dG(u)+1. In the present paper we conjecture the stronger bound α(G)≥∑u∈V(G)2dG(u)+ωG(u)+1 where ωG(u)ωG(u) is the maximum order of a clique of GG that contains the vertex uu. We discuss the relation of our conjecture to recent conjectures and results concerning the independence number and the chromatic number. Furthermore, we prove our conjecture for perfect graphs and for graphs of maximum degree at most 4.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 59–67
نویسندگان
, , , ,