کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649518 | 1342458 | 2010 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Triangle-free graphs whose independence number equals the degree Triangle-free graphs whose independence number equals the degree](/preview/png/4649518.png)
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.
Journal: Discrete Mathematics - Volume 310, Issue 3, 6 February 2010, Pages 662–669