کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649518 1342458 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Triangle-free graphs whose independence number equals the degree
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Triangle-free graphs whose independence number equals the degree
چکیده انگلیسی

In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class SS of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph GG must be regular of degree d=α(G)d=α(G) and the fractional chromatic number must satisfy χf(G)=|G|/α(G)χf(G)=|G|/α(G). We indicate that SS is a rich family of graphs by determining the rational numbers cc for which there is a graph G∈SG∈S with χf(G)=cχf(G)=c except for a small gap, where we cannot prove the full statement. The statements for c≥3c≥3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c<3c<3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in SS like chromatic number and toughness.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 3, 6 February 2010, Pages 662–669
نویسندگان
,